26

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

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

P#19251 2016-03-15 22:24 ( Edited 2018-08-09 06:50)

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?

P#19252 2016-03-15 22:29 ( Edited 2016-03-16 02:30)

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.

P#19254 2016-03-15 22:50 ( Edited 2016-03-16 02:50)

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!

P#35041 2017-01-05 21:14 ( Edited 2017-01-06 02:14)

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

local y = index - (x*w)

P#46599 2017-11-22 20:34 ( Edited 2017-11-23 01:34)

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.

P#46613 2017-11-23 02:30 ( Edited 2017-11-23 07:30)

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

P#46620 2017-11-23 07:45 ( Edited 2017-11-23 12:45)

Oh, the map/grid/maze/whatever.

P#46654 2017-11-24 03:29 ( Edited 2017-11-24 08:29)

@Felice
Thank you!

P#47270 2017-12-11 03:55 ( Edited 2017-12-11 08:55)

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?

P#47709 2017-12-27 18:18 ( Edited 2017-12-27 23:18)
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!

P#54891 2018-08-09 02:50 ( Edited 2018-08-09 06:50)