Log In  



Cart #19253 | 2016-03-16 | Code ▽ | Embed ▽ | License: CC4-BY-NC-SA
27

A* pathfinding example made for the pico-8 fan zine!
(just an example, modify the code to move the points)

27

Excellent example! It's interesting though that it doesn't find the shortest possible path, which would be 20 moves, whereas the path it highlights here is 21 moves. I wonder why it chose to move down, left, then back up in the middle there when it could have just gone left-left?

Thanks for that, I didn't notice, I was missing the cost per move which was messing it up. Made it so each move costs 1.

Thank you for this example! I'm new to Pico-8 and Lua so this taught me some language features that I wasn't up to speed with as well (such as multiple return values). I Managed to get your code up and running in my little cart I'm working on.

Great tutorial in the Pico Fan-Zine as well!

In the function indextomap, what does 'w' mean here?

local y = index - (x*w)

@Tinglar:

That's typically the w)idth when indexing a one-dimensional array that represents a two-dimensional grid.

The math is always some arrangement of i=y*w+x.

@Felice:
…the width of what, I meant?

Oh, the map/grid/maze/whatever.

@Felice
Thank you!

what does it return if there is no possible path? like if there is a wall or something that makes it impossible to reach the goal?
6

Maybe everyone already figured it out, it took me a shameful amount of time to solve this. I know this is a massive bump, but I wanted to share this modification for others. I spent too long poking it trying to make it work in my own project before I figured out that it chokes if no path exists.

(The crash was a bit confusing to me, since pico8 takes me to the vector parsing function, while the real problem is actually from running the path searching on a map with no goal found by the frontier array.)

You can make this stop crashing if no path is found by doing the following minor changes. Along the way you get a bonus variable to check for if the destination even is found, and a more "noob friendly" starting kit.

  1. Before running the while loop for frontier, set up a boolean
 
found_goal=false
  1. In this part of the code, where the frontier search breaks itself, also set your bool so we know the exit existed in the search. This is found right near the top of the while (#frontier > 0 loop. Add the found_goal=true line.
 
if vectoindex(current) == vectoindex(goal) then
   found_goal=true
   break
  end
  1. Now wrap everything from the printh("find goal..") line to the map drawing part at mset in an if statement like the following:
 
if found_goal then
 printh("find goal..")
 current = came_from[vectoindex(goal)]
 path = {}
 	local cindex = vectoindex(current)
 	local sindex = vectoindex(start)

 while cindex != sindex do
  add(path, current)
  current = came_from[cindex]
  cindex = vectoindex(current)
 end
 reverse(path)

 for point in all(path) do
  mset(point[1],point[2],18)
 end

end

Tada! Now the example won't crash if you draw walls with no route to find. Instead the exploring part of the path finding just fills the existing space, and the path searching will skip. If you end up using this code for your own calls, you can always check the found_goal to avoid running any AI or change behavior when no route is found.

I hope this helps someone else avoid spending all evening running in circles. Cheers!

@darkgriffin This is very kind, thanks for sharing! I was stumbling over that problem and then decided to write my own-albeit less effecient-aStar implementation. I do need an optimized function though, so maybe I'll switch back to this with your changes incorporated. Thanks for sharing!



[Please log in to post a comment]