LoveAStar: A* Search in Lua/Love

[MarekkPie]

All this talk about maps/mazes and maze creation made me want to design a maze solver. I went with A* search because there was a nice tutorial in both the Wikipedia page and this webpage.

wkVxm.png (29.62 KiB) Viewed 840 times

Updated 1/13/12:
Even more optimization, and a "final" release. It's also completely abstracted from any particular map, so you can make square maps, rectangular maps, hexagonal maps, circular maps, atlases, possibly even 3D space. Since I require you to shrink everything into a 1D array before use, the rigidity of the map doesn't really matter.

I've created a GitHub to handle this stuff: as I feel having the delete the old file and re-upload the new one here to be a bit of a pain.

Just the demo Updated for 0.8.0:
https://github.com/downloads/mkosler/Lo ... AStar.love

The full GitHub:
https://github.com/mkosler/LoveAStar

The control for the demo are on the GitHub page, but I'll republish them here:

CONTROLS FOR THE VISUAL DEMO:

MOUSE:
Left-click: places the start node (green rectangle)
SHIFT+Left-click: places a wall
Right-click: places the end node (red rectangle)

KEYBOARD:
W: toggles the drawing of the walls
M: toggles the ability to change the map (which stops the calls
to flattenMap(), to show the speed of A*)
TAB: calls A* once
F2: resets the program
P: toggles the stress test
[: Decreases the number of consecutive calls to A* during
the stress test (clamped at 1)
]: Increases the number of consecutive calls to A* during
the stress test (clamped at 10 with a dynamic map/100 with a static map)
ESC: Quits the program

I added the ability to call the algorithm multiple times in succession, so you can see how it would perform with multiple entities all needing to call the algorithm.

I added in the ability to freeze the current map, so you can more easily stress just the algorithm as opposed to the algorithm AND the flattenMap() function. Ideally in a game, you would only need to flatten your map when a wall changes (the algorithm already takes into account changes in the exit node position), so it gives a better understanding of the limits of A*. On my Dell XPS 8100, a got about 62 consecutive calls while staying about 30 FPS when I froze the map. With a dynamic map, using my poorly optimized flattenMap() function, I think I hit only 4 consecutive calls to both flattenMap() and A* before I dropped below 30 FPS.

Included in the GitHub are instructions on what is required for LoveAStar. I also made a small helper constructor for the nodes used in the A* array, so any flattenMap() function can just load the necessary information into that constructor and not have to worry about implementation. I also made sure I commented the flatten.lua and astar.lua files, so hopefully it'll be fairly easy to understand. If you have questions or need help implementing it, feel free to reply to this post. I also added a binary heap for one of my sets, so you will need the binary_heap.lua file to run LoveAStar.



Links to pathfinding optimization articles (who found the article will be noted in parentheses):
http://www-cs-students.stanford.edu/~am ... html#paths (coffee)
http://doryen.eptalys.net/data/libtcod/ ... index.html (coffee)
http://www.gamasutra.com/view/feature/3 ... hp?print=1 (coffee)
http://harablog.wordpress.com/2011/08/2 ... -breaking/ (MarekkPie)
http://www.policyalmanac.org/games/binaryHeaps.htm (MarekkPie)

[coffee]

Congratulations and thanks for this. There is some LOVE A*path findings around like this one (http://love2d.org/forums/viewtopic.php?f=5&t=3459). And all seems work well like yours. The problem is that later aren't flexible to adapt to other people maps (define obstacle values, check walkable or instead non-walkable, check and make paths in multi-layers, etc).

I like how you comment very well your code. Thank you because this is good to learn how to do a-path code.

EDITED For a better testing it be good a key to reset the path calculation but not the origin/destination and obstacles.

[Robin]

Also, middle click is a bit awkward on my laptop, and it would be nice if we could remove obstacles as well.

[coffee]

Also, middle click is a bit awkward on my laptop, and it would be nice if we could remove obstacles as well.

I was to "complain" of that in first draft of post, Mac use middle button for Dashboard but since I don't really use/like it much I preferred disable that option to keep 3rd button free (F4 it's enough).

[MarekkPie]

I believe there is the ability to remove obstacles, just by middle-clicking them again.

How would you implement a SHIFT+left-click?

Code: Select all

function love.mousepressed(x, y, b)
  if b == "l" then
    if love.keyboard.isDown("rshift", "lshift") then
      -- shift click implementation
    else
      -- regular click implementation
    end
  end
end

Would that work?

[bartbes]

It should, but wasn't the vararg isDown introduced in 0.8.0 (making this incompatible with 0.7.2)? Sometimes these changelogs all become a blur..

EDIT: Nope, never mind, that was 0.7.2.

[MarekkPie]

Added a second .love for those of you on notebooks or with ancient mice. The obstacle placement is changed to SHIFT+left click.

[Robin]

Added a second .love for those of you on notebooks or with ancient mice. The obstacle placement is changed to SHIFT+left click.

Thank you.

[coffee]

MarekkPie, pressing TAB twice gives error (I was looking if there was now a button to clear path but not the defined positions)
Also it's possible to get a path only defining one point but the other opposite red/green square at 0,0 is not drawn (not really a bug, don't know if intended or you forgot draw the square).

[MarekkPie]

MarekkPie, pressing TAB twice gives error (I was looking if there was now a button to clear path but not the defined positions)
Also it's possible to get a path only defining one point but the other opposite red/green square at 0,0 is not drawn (not really a bug, don't know if intended or you forgot draw the square).

Working on the first part. I need to flush the map but then rebuild it, but my current implementation only toggles the attributes of the map upon a mouse event, so it doesn't quite work that way. I suppose I could make an additional layer above the A* layer that has the attributes, then flatten the layers once it's time to start pathing.

The second is just a "my bad." The oldStart/oldExit need to be initialized to 0,0 instead of 1,1, and then put a guard on the mouse click event since 0,0 doesn't exist on my map, so you'd be indexing a nil value at some point.