Hi all, I have finally come to the decision to create my own pathing algorithm for faster path analysis. I am using a modified version of a* for my pathing. For the most part, the pathing works, it is able to return the shortest path. However, there are 2 things that I am in need of help.
First, how does one recreate the ‘zig-zag’ pattern that the units have to take? With most pathing algorithms, it doesn’t matter what path it takes, as long as it is shortest, but terminal requires the units to prefer alternating between vertical and horizontal movement where possible. I have tried adding a penalty if the path uses 2 vertical or 2 horizontal movements in a row, and it does lead into a zig-zag motion, but it isn’t perfect. I have also considered getting all the paths that have the least number of steps and then choosing the path that fits terminal’s pathing algorithm, but that would require many more path calculations. How have other people managed to recreate the zig-zag motion?
Secondly, since the unit’s has a series of end locations (along an edge) rather than a single point, the end location will be changing after each step the unit takes. I do have a solution, which seems to work, but I am unsure due to the nature of the solution, and that this might be contributing to problems explained above. After each step, I recalculate the edge location that is the closest to the current location (euclidean distance). That will be the target location. I’m quite sure this works most of the time, but I don’t know how this would handle complex maze algo layouts. Am I doing this part correctly? Or is there a more simpler approach to this?
Any help would be greatly appreciated. I am in the process to creating a highly adaptive algo (similar to @Aeldrexan’s Aelgoo series), and I’m finding the built-in pathing algorithm is painfully slow 
.
Before version 54, Aelgoo was using a modified version of Dijkstra’s algorithm.
To make it zig-zag, I was just adding the neighboring tiles in the correct order in my list of locations to examine.
I don’t think this is possible with A*: basically this method forces the order examination of the tiles to match the correct pathing preferences of the engine, while A* is choosing an order of examination that seems the best for a quicker pathfinding.
While Dijkstra is slow compared to many other pathfinding algorithms, I was able to compute a path in 2ms on average on my laptop (twice as fast in the playground). You can see here (thanks @876584635678890!) that Aelgoo was already doing pretty good, for instance Aelgoo51_UFO was number 2 (just after your algo…) for several days around November 10.
Since Aelgoo54_CARDS, I do something way faster than both Dijkstra and A* (and that is still 100% correct), but I won’t explain it (sorry 
).
Anyway good luck with your adaptative algo 
.
2 Likes
I see. I initially chose to do a* because it is faster, but I see why dijkstra’s algorithm may be better suited for this situation. I’ll give it a go, thanks for the info!
1 Like
Before you give up on A* I wanna tell you that I used it (without heuristics) for my pathfinding and it takes about 1s-1.5s to calculate 5000 paths on changing maps.
You can give each tile on the map a distance value using A*. To get it to work with several endpoints, just put every edge location into the open list for the A* algorithm in the beginning. These values should be “cached” while the map doesn’t change. After that, you can determine the direction for a tile by looking at the distances of its neighbors and getting the 2 lowest distance neighbors:
- If both share the lowest distance and they are on different directions of the current tile (vertical and horizontal neighbors), look at the last direction the unit moved and take the one that is not on the same axis.
- If they are on the same axis (both horizontal for example), take the one that is nearest to your target side (closer on y for vertical and closer on x for horizontal)
- If there is only one lowest distance neighbor, take that neighbor
What direction to take for each tile can be cached as well to get even better performance.
You can then easily calculate any path by looking at the cached directions until you reach an edge.
But there is still one thing left to get a correct path. You have to take into account that not every location can find a path to the target edge. So after you did the initial A* calculations for the target edge you have to look for locations that are not yet looked at depending on your target edge. You have to do this before you calculate the directions.
To do this you have to iterate over every location and check if it already has distance value assigned. If not, just do the A* thing again but initialize the open list with that location.
You have to look at all the tiles in the right order for each target edge because self-destruct points are chosen as follows:
- closest y location (for example you want to go to the top right edge, you take the biggest y value)
- closest x location
So to do this you just iterate over y first and then over x and start with ARENA_SIZE or 0 depending on the target edge. For example, if you want to get to the top-left edge:
for y in range(ARENA_SIZE-1, -1, -1):
for x in range(0, ARENA_SIZE, 1):
# check and do A* if needed
Now you have everything calculated and ready as long as the map doesn’t change. If the map changes tho you have to recalculate everything. You can save some time by thinking about what has to be recalculated when you add a firewall or remove one but I won’t tell you exactly what to do (one tip: calculate priorities for each tile depending on their x and y pos. This will help you if you break a firewall between a region that will lead to the target edge and another that would lead to self-destruction. Just copy the priority value over to other locations in the A* algorithm)
If you choose to take the A* approach, be warned that the optimizations to get to 1s-1.5s for 5000 paths will take some time and many MANY bugfixes.
Sorry for this text wall and I’m not even sure if it is still A* after removing the heuristics but I hope this will help getting started with that approach.
I can tell you more details after the global competition 2018 ends to not give away too many of my secrets after weeks of work on this.
1 Like
I did about the same as you with similar results.
I’m not even sure if it is still A* after removing the heuristics
To me A* without heuristics is Dijkstra. And I definitely don’t think this approach of making a map of distances should still be considered Dijkstra or A*, even if it uses Dijkstra’s algorithm as an initialisation.