LoveAStar: A* Search in Lua/Love

[coffee]

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.

That's ok, don't hurry or worry. But you could easily resolve for now "TAB twice" error setting a flag after path is draw (to disable a second TAB press).

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.

For something forgotten I really think you can use this "error" to present a default assignment of path between 1,1 and the chosen destination/origin.

BTW You doing a nice work on this.

[MarekkPie]

Updated the .love again to allow for changing maps after the initial path finding. I also just map SHIFT+left click the default obstacle placement.

It actually wasn't that hard at all to make the game allow for changes. I just map a second layer that holds the triggers, then once you hit tab, it loops through the trigger map and toggles those values (start/exit/wall) onto the pathing map. Now you can change the trigger map as much as you want, since the pathing map doesn't read from it until right before you start pathing.

The problem with leaving the error would be if someone were to implement this into say...a game like Dwarfs!?. If there was a default path, then all the enemies would try going to that path, which may be unreachable/leads to death/in the opposite direction of their objective. I'd rather they just sit dumbly than do that.

[coffee]

Updated the .love again to allow for changing maps after the initial path finding. I also just map SHIFT+left click the default obstacle placement.

Oh nice work, I think it's almost perfect now. It's possible and easy to readjust things now without do all again. Perhaps only thing missing is to erase the draw path when we change something or perhaps better than that redraw the path with new calculations without even press TAB (on-the-fly).

[MarekkPie]

Oh nice work, I think it's almost perfect now. It's possible and easy to readjust things now without do all again. Perhaps only thing missing is to erase the draw path when we change something or perhaps better than that redraw the path with new calculations without even press TAB (on-the-fly).

Well, it already has that capability. It's the visual demo that is restricting it. I wanted someone to have time to look at the path, and maybe predict the route, before the algorithm does the calculation.

As long as you have a rectangular based grid with a start position, and exit position, and wall representations, you can run the algorithm. The demo makes the call to the algorithm via key press, but you could pretty easily make the call every time the exit moves (aka the player), a wall gets added, whatever. I suppose I could lift it a bit more and figure out how to deal with other tessellations to make it even more usable. In my mind, it would need to be a uniform tessellation (aka only one polygon is tiled) in order to make a "fairly" easy jump...

I'll start thinking about that.

[coffee]

Well, it already has that capability. It's the visual demo that is restricting it. I wanted someone to have time to look at the path, and maybe predict the route, before the algorithm does the calculation.

If people wan't to look at path first they just would need to don't change nothing first. I'm trying to get flaws in the routes, didn't get any errors till now, only got alternatives routes with same number of steps which I only didn't know why it choose go by the other way. Seems all working well. Congratulations.
Note. Maybe could be useful you also print the number of the steps on a path.

[Jasoco]

How fast is it, is it faster than the older A* we had? I would need one that can run its pathfinding in the background, either by a thread or alternate method of calculating its path while still allowing the rest of the game to update so I can have multiple objects moving at once but instead of one object pausing the whole program while it finds its path, itself would only pause while the rest of the game updates.

[MarekkPie]

Haven't even looked at the speed. Wouldn't know where to begin. Made it mainly as just an exercise.

Right now the algorithm and the visual demo are on the same file, so you'd need to crop out the algorithm in order to implement it in a LOVE thread (as far as I understand. I haven't looked at them all that much.) Luckily, the algorithm isn't intertwined with the other code in the file. There's a big block of commented equal signs separating the two.

[coffee]

How fast is it, is it faster than the older A* we had? I would need one that can run its pathfinding in the background, either by a thread or alternate method of calculating its path while still allowing the rest of the game to update so I can have multiple objects moving at once but instead of one object pausing the whole program while it finds its path, itself would only pause while the rest of the game updates.

Good question. Well in turn-based we don't need for sure worry. But with your realtime case it's better probably you do some tests first to find an average acceptable recheck time. I guess checking the FPS values will give a clue. Also you can do some tricks like disable apath when you don't move, or give some reaction time delay in enemy pathing just like in real life someone don't react right away and wait to see if you are trying to fool him.

EDITED. Couldn't MarekkPie put a dt to count the timed used since the engine began to make the calculations?

[Jasoco]

Obviously the way I think about it, an enemy or player object would have a "thinking" state.

They'd start "standing", then say they find a target they want to move to, they set their target square and call the A* algorithm, then, while the character is "thinking", the algorithm instead of being a self-contained loop would be a function you call over time and every time the function is called it calculates the next step of its pathfinding. It would be able to run simultaneously parallel to the rest of the game and wouldn't cause pausing.

One day I'm going to sit down with one of these A* demos and try and see what I can do with it.

Threads are one option I guess. But I have no experience with them at all.

[MarekkPie]

Just thinking off the top of my head, you can reduce the number of calls to A* by realizing when you actually need to recalculate. When the enemy, standing on the start node, moves, you don't need to recalculate since he is following the best path from any of the nodes on the current path to the exit node (the player). For deformation of walls, I feel as if there might be a way to trim it, but I keep running into exceptions to my rule, so I am going to keep it to myself for now.

So given that, we must make a recalculation every time either a wall is deformed or the exit node moves. But you can do a few more things to reduce the number of calls to A*. A* is only useful if there is an obstacle between the enemy and the player. While the enemy is, let's say, on the same screen as the player, you could do small "selection" checks to see if there are any obstacles. For example:

nBsHfl.jpg (30.34 KiB) Viewed 485 times

In this case, you run a small check of the nodes in the highlighted area, and if there is no obstacle, then a much simpler pathing algorithm takes over, like simple alignment (if a.x < b.x then...etc...)

b9eaGl.jpg (29.16 KiB) Viewed 485 times

In this case, you run the check until you hit an obstacle, at which point you tell the program to continue using A*.

GdXrpl.jpg (125.33 KiB) Viewed 485 times

The other situation would be at great distances. At that point, you are only using A* to really get "close" to the exit node, as opposed to right on top of it. As long as the player stays within a reasonable distance to its exit node, you don't need to update the path with A*.

Making the calls to A* in a separate thread still seems like a good idea, but using the above to trim the number of times you actually make that call will help performance as well.