Tutorial 15 - A* Path Finding and a Simple Level Editor

Tutorial 15 is out now at the usual spot (http://codeatuts.blogspot.com.au/). It covers some interesting ground starting with an implementation of the A* path finding algorithm. To demonstrate this I created a simple level editor called dGenerator. I’m quite happy with how this came out and will continue to develop it with the eventual aim of creating a tower defence game.

The next step will be to allow the levels to be saved and then loaded into your game using saveGlobalData(). At this stage I’m thinking of converting the grid table to strings to save it and then reversing the process when loading into the game. I would be interested if you folks had any other ideas about how to approach this.

As an aside I’ve included a class in dGenerator which implements a button class using sprites as this was a question somewhere else on the forum.

All the code and graphic assets required can be downloaded from the tutorial. The sprites were done on the iPad using Sprite Something (great App).

This what dGenerator looks like: http://youtu.be/zfJKz_1uGa8 (the video resolution doesn’t really do it justice)

hey @Reefwing i was reading your tutorial and couldn’t see the link for the dGenerator sprites. specifically, section 15.4, number 8

.@veeeralp - sorry! Should be there now.

The link is: https://www.dropbox.com/sh/1ob7dp6itdefraw/8JO3CRn1if

@reefwing

Had a look at the source for the button and I see this


   -- Initialise Button

   self.x = x or 0
   self.y = y or 0
   self.pressed = pressed or false
   self.text = text or ""

   -- Images from dropbox? Why not local?
   self.normalImage = readImage("Dropbox:Button 64x64px")
   self.pressedImage = readImage("Dropbox:pressedButton 64x64px")
  
   self.w = self.normalImage.width
   self.h = self.normalImage.height
   self.tag = nil
   self.action = nil

Where the code is looking for the images in Dropbox - is that correct? If so, could you post some replacement code where it looks for the images on the local iPad - maybe in the included local sprite pack?

Hi @bernbout - the code is correct. I used custom sprites for the buttons which you can download using the link above.

If you don’t want to use my custom sprites then just tap on the text e.g. “Dropbox:Button 64x64px” and select another sprite from one of the standard ones. My sprites are 64x64 pixels so try and use ones roughly the same size (e.g. “Cargo Bot:Register Slot” is close enough).

No extra code is needed to make this work.

Funny, I just did something similar with A*!

.@aciolino - great minds…

I’m impressed with how well the algorithm works. It is very quick.

Yeah. It’s fast. I have it on a 50 by 50 grid, with tens of items moving…it starts to slow down after that point, especially when I was drawing each sprite as a separate call in draw().

I read about some precomputing stuff that helps when there is a fixed path, and also came across someone who precomputed all possible paths from each point and loaded the data as an asset and used a lookup table. That seemed a bit overzealous for my needs.

@Reefwing hi. I’ve looked at your tuto on path generator. Very nice! I was wondering if you would be so kind to pack all the files in 1 zip and put the link in your blog? it is much easier to download then than do it file per file (ok, i am a bit of lazy lad :"> , but there is no harm asking? :smiley: ).

.@aciolino - that is interesting. I hadn’t tried it with multiple objects calculating a path. Are you sure that it is the algorithm and not the sprite drawing which is slowing you down?

.@Jmv38 - thanks dude. It is already there, check out the first file in the list called dGenerator v1.lua - the description gives it away “The complete code in one file”. It isn’t zipped but then it isn’t a big file. Here is the link: https://www.dropbox.com/s/tts3hsp9iigqyf6/Tutorial_15_dGenerator_v1.lua

Hi,
First of all, thank you guys for your contributions !
I m trying to execute the dGenerator but, unfortunately, I obtain an error msg on line 168 : attempt to perform arithmetic on global ‘spriteSize’ …
I stop and then I click on run (remote buttons on the left) and it works …
A problem with my Codea ?

Hi @Godzilla,

Thanks for the feedback. I think the issue is that the latest version of Codea (v1.5) has changed the order that functions are run. The function orientationChanged() now gets called before setup(), so if you try to access variables in orientationChanged() which are defined in setup(), it is a problem. This is the way that the Lua code works in the runtime, so it makes sense to have it consistent.

The fix is simple:

  1. At the start of the program in the Main tab (just beneath the line supportedOrientations(ANY), add a new boolean as follows:
setupHasRun = false
  1. In setup() add the following as the last statement before the closing end:
setupHasRun = true
  1. Finally, in the function orientationChanged(newOrientation), make the following changes:
function orientationChanged(newOrientation)

    if setupHasRun then

    -- This way we don't try to update the grid location until after setup()
    -- has been run. Note that updateGridLocation() calls spriteSize which 
    -- is defined in setup().

    updateGridLocation(newOrientation)

    end

end

```

Hi@Reefwing and @Godzilla,

I too had the same problem. The error involved refers to spriteSize being reserved word (and the text colour shows this). Changed text throughout to sSize but still an error in the function set up for adjustments due to changes in orientation - not sure why. Also you need to add your own sprites as the ones referred to in the script are on Reefwings DropBox account.

Managed that but stuck with the orientation issue.

Thanks for the code Reefwing.

Bri_G

:slight_smile:

.@Bri_G - I think we posted simultaneously - see if the above suggestion fixes the problem. It does for me. My local spriteSize probably overrides the global one but I agree that using a different name is less confusing and better practise.

Alternative, define your function as _orientationChanged and at the end of setup put orientationChanged = _orientationChanged. Avoids evaluating an unnecessary conditional on every run.

Good idea @Andrew_Stacey

Hi Reefwing,Bri_G,Andrew,
That works well now and, thanks to you, I’ll dig a little bit more to understand what is below (i.e. How Codea do things).
You point also the fact that a futur update of Codea isn’t harmless…
@Brig : the spriteSize is not an issue here even if it’s a Codea function.
@reefwing: do you know how to modify your code to use diagonals?

.@Godzila - A* pathfinding works on diagonals but I haven’t written the code for it. You need to allow movement in that direction and do a bit of math to calculate the diagonal distance.

@Reefwing: I ll try to take the time to handle it and i ll give u a feedback. Thx.

.@Godzila - excellent let me know how you go.