LÖVE

coffee wrote:I agree with Robin, there is a very strange delay even that the path have a lot of steps. The engine shouldn't take so long calculating since the engine haven't real alternatives or new bifurcations to compare with old path. But the engine is probably rechecking after a new step again and again if tiles in his "back" are still an alternative.

It might seem like that's the case, but A* doesn't work that way. Once it explicitly tests a node, it removes it from the "open list," which is where it would look for a new node to test. So A* doesn't backtrack in this scenario.

I think I found out what the problem was, and it might have little to do with the actual algorithm (though I still will probably optimize that). I have a function called "flattenMap()" which I threw in to allow for updates in the layout. Right now, it loops through the entire map, every time, before the start of the search, and like a big hand, rubs itself all over the map, checking every boolean toggle and comparing it to the boolean toggle on the "visual" map. The reason I think this is the issue is because walls were a part of my flattenMap(), and it needed to switch the wall toggle on for half the nodes on the map, every dt (during the speed test).

I can probably optimize this by only doing the big sweep once, and then sniping only the toggles that matter. This might take some time, because I'll probably end up rewriting a big portion of the A* neighbor check.

This path isn't the short '-'.

Yes it is. If you were a player, could you go between those walls?

Mkalo wrote:

This path isn't the short '-'.

Yes, it's one of the shortest. But yes, there another valid alternatives. I noticed Marekk engine have a kind of "flavour" for finding his way. He likes choose more "straight" ways than the ones that are more "stealthy" getting around closest to walls.

MarekkPie probably you already know this but you can find awesome tips for improving things here
http://www-cs-students.stanford.edu/~am ... html#paths

EDITED

MarekkPie wrote:Yes it is. If you were a player, could you go between those walls?

Hmmm, actually some (probably a lot) roguelikes would let you pass. (I now see what Mikalo want to say). But isn't your fault MarekkPie

EDITED2 Probably you could make a "switch" for "diagonal" walk

There are some bugs that pop up in that build, that mainly deal with my hackish way of avoiding corner cutting. For a game, you HAVE to avoid corner cutting, since the player object has some size that may clip into the wall. My method was a bit funky, mainly because at the moment I am trying to avoid the pitfalls of using absolute direction (and because I wrote that part at 3 AM).

But that is THE shortest path with squares. The distance between the center of a square and the edge of a square isn't uniform like a circle. Also, unlike a hexagon, squares share positions with different neighbors at its corners. A square has 8 neighbors and a hexagon only has 6. The distance to reach the corner from the center is the length of the hypotenuse of a 45-45-90 triangle (sqrt(2)). To reach the center of an edge is the length of a leg of a 45-45-90 triangle (or 1). I smoothed out the calculation by making the distance to the diagonal neighbors 14 (since sqrt(2) = 1.414) and the distance to the orthogonal neighbors 10 (per the advice of one of the website I linked to in my original post).

So, if I were to "hug" the wall like in the picture, I will have traveled 10 for the downward move and 10 for the move to the right, 20 total. By going diagonal, I only moved 14, which is clearly shorter.

download/file.php?mode=view&id=22516
One call

download/file.php?mode=view&id=22517
Seven calls

And there we have it. Significantly better than before. I rewrote the program from the ground up, because I was having to duct tape every inch of the original program, and eventually, I hit a bug that I had absolutely no explanation for because of it. The A* search algorithm is also much more detached from the map than it was before. It has support for any arbitrarily shaped map (squares, rectangles, hexagons, world maps, 3D space (well maybe...), whatever), you just have to build a flattenMap() function to accommodate it. I'll write a little blurb about what is required to implement it. If you don't want the hassle of making your own flattenMap(), I've packaged a non-optimized version to flatten a square map

As you can see from the images, a single call has no impact on FPS, even in our worst case from before.

As an aside, the worst case in my new implementation is actually a straight diagonal line, since the number of open nodes to search through for the next best guess is far larger than anything inside the swirl case. My problem with the original implementation was during the buildPath() phase at the end of the algorithm. Previously, I just searched through the entire closed set of nodes (the nodes that I had explicitly tested to see it was the exit node), pruning the closed set only if it was a parent to the path nodes. For the above case, that meant looping through at most 312 nodes every time I didn't find my way back from the exit node! Which for the above case, meant I had to check 48516 times! Now, when I assign a parent, I also assign its location on the closed set. So now, I only have to check at most 312 times!

I did a few more tests with different modules turned off, as well as turning off vsync, and the most it helped was maybe 1 more call was capable before it dropped below 30 FPS.

Keep in mind that all of these FPS numbers also take into account the graphics and my flattenMap() algorithm, which can clearly be improved upon, and should be something that you build yourself inside your game.

This is probably the most optimized I, alone, can get the A* search without moving to like C or something closer to the hardware. There are plenty of ways to accommodate for more enemies using A*, which have been linked to or posted on in this thread, but for just a straight up stress test, this is the best I've got. When I upload the "finished" version, I'll probably add a few links to that stuff on the original post.

EDIT: Here's a sneak peek at it before I update the first post. Most of the controls are the same.

Left click places the start position;
Right click places the exit position;
Shift+left click places a wall;
F2 resets the map;
TAB runs the algorithm once;
P toggles the stress test;
[ decreases the number of calls to the algorithm during every dt;
] increases the number of calls;
ESC quits.

Nice work MarekkPie you fixed the "one-way" delay. Question: How we switch from now on from the "diagonal-cheating" to old "need one space to cross" mode?

Note: Now that you dimmed the grid and reduced the point size is a lot hard count the number of squares.

And BTW if you confortable with C variants or Python you can check how Litcod deal with astar and dkstra
http://doryen.eptalys.net/data/libtcod/ ... index.html

Also useful to you (note: this is a very good article)
http://www.gamasutra.com/view/feature/3 ... hp?print=1

The block against slipping through diagonals was pretty whack on my first version. And in reality, that part has little to do with A* and more to do with aesthetics, so I removed it from the algorithm. When you make your own flattenMap() style function to send it to A*, the way you would deal with that (or at least the way I initially dealt with it was):

• Build your list of neighbors;
• If there is a wall in your list of neighbors, check it's relative position to you;
• If the wall is orthogonal to you, remove from your list of neighbors both the rest of the nodes on that side.

I can look into bringing it back for my flattenMap() demo, but that has little to do with A* and more to do with what neighbors you give each node BEFORE A*. When I release the better annotated version, hopefully it'll explain better.

Updated the first post with the fully optimized version. Made a small change from the above version and the one on the project's new GitHub page. I moved from a simple table handling my open set to a binary heap, which seemed to reduce the time spent searching through the open set for a new node to check. Lua already uses quick sort, but a binary heap really only cares about placing the minimum (or maximum) value at the front of the array, and leave the rest as a semi-jumbled mess.

I also made a LoveAStar library page, which can be found here:
http://love2d.org/wiki/LoveAStar

It won't lead you to anything excitingly different than this thread will, but it has a few selling points in it.

It's already suitable for use as library? That was fast! Congratulations. I'm not ready yet to use it in my tile engine now but I will for sure in a couple of weeks test it. I think Jasoco and Nixola that already tested LuStar would love this