Question about pathfinding in a particular context

[lulero]

Hi! English isn't my native language so I hope this won't be too hard of a read.

I'm working on a roguelike project, written using Java, as a learning experience. Right now I'm trying to decide on a pathfinding algorithm that would fit my settings.

Here are (I think) all the relevant aspects:

• A level is made of (at most) 40x40 tiles.
• There is no fog of war.
• Some maps layout might be maze-like.
• Monsters spawn continuously.
• Can have up to about 100 monsters at the same time.
• Most monsters will track the player no matter how far they are.
• The player has access to summoning abilities.

Also relevant are the possible tile types:

• Basic. No restrictions.
• Wall. Blocks all movement.
• Shallow water. Shouldn't matter for pathfinding. Even if it slows some mobiles the shortest path is decided on the number of moves.
• Deep Water. Need to be flying or able to swim to get through.
• Lava. Need to be flying or fire immune to get through.
• One way. Basic tile that forbid movements from a given direction. Need to be flying to get through from the wrong side.

IMO why choose Djikstra over A*:

• Relatively small maps.
• Lots of simulatenously tracking monsters.
• Maze-Like maps.

IMO why choose A* over Djikstra:

• Summons (some mobiles can track something else than the player).
• Variety of tiles with different restrictions on movement depending on who's tracking.

Another option: A* with "helpers". I'm not sure how to do that, but those pathfinding "helpers" would be computed during map loading/generation. First by identifying "areas" and then how to get from one to another. An area is a subpart of the map where A* works great (no need to move backward). Sounds complex but if I can pull it off it should be efficient. A bit worried tho on how the movements will look when, say, the player and the monster tracking him are close but in different areas.

My plan at the moment is to go with Djikstra for monsters, some kind of A* for summons, and see how it goes. However pretty sure it will be slow as I'll have to run the algorithm several times each time the player moves (because of tile types). Thoughts?

[Z]

If your allies just target the nearest enemy, or all target the same enemy, then this can be solved by another instance of Dijkstra (if they target the nearest, just start Dijkstra with all the targets as sources). With just six types of monsters (walking/fire resistant/flying and enemy/ally) and 40x40 maps this should still be extremely fast. BTW since you seem to assume that each tile can be walked in time 1 (even the shallow water) BFS should work, and it is simpler to implement and faster than the general Dijkstra algorithm.

I think your method might not be clear to some people (you are either running A* for each monster, or Dijkstra once per each class of monsters which have the same goal and mobility).

[lulero]

if they target the nearest, just start Dijkstra with all the targets as sources

Genious. Several source, why didn't I think of that? That solves the summon issue and opens my mind to a lot of possibilities, thank you.

BTW since you seem to assume that each tile can be walked in time 1 (even the shallow water) BFS should work, and it is simpler to implement and faster than the general Dijkstra algorithm.

From what I understand, BFS is like a regular Dijkstra that stops once the "target" is found. However I have multiple targets (trackers). I can stop once all the targets are reached. Problem, what if the best path for a given mobile is blocked by another one? My current idea was to take the second best option but there might not be one computed yet. Or I can take neighbours tiles as targets as well, guess it would work and be indeed faster.

Both points are similar, multiple source and multiple targets. Also gives me ideas on how to implement this still foggy idea with pre-computed pathings from an area to another.

I think your method might not be clear to some people (you are either running A* for each monster, or Dijkstra once per each class of monsters which have the same goal and mobility).

Indeed wasn't very clear, but you got it right.

Thank you Z!

[Z]

BFS (Breadth First Search) is an algorithm used to determine the distance from a given vertex in the graph to all vertices, where the distance is the number of edges. It is implemented with a simple queue. You can stop it once you reach the target if you want, or not stop it if you do not want.

Dijkstra algorithm is similar, but now edges are allowed to require different times to traverse. You need a priority queue instead of a simple queue, so it is a bit more complicated to implement and also a bit slower.

A* is similar to Dijkstra, but optimized for reaching a specific target.

I am not sure what you should do when the best path is blocked by another monster, in my games (Hydra Slayer, Hyperbolic Rogue) blocked tiles are treated as impassable, but this sometimes gives some quite strange results (monsters stop following or try a much longer different route when blocked). Another option would be to treat them as passable (so they simply wait in a queue) or treat them as passable in, say, 5 turns (this will make blocked monsters try the second route if it is not much longer, and wait in a queue otherwise).

[lulero]

About BFS it's pretty much what I had in mind when I mentioned Dijkstra as I didn't plan on taking time required to travel into account. When looking it up on wikipedia the only difference I saw from my way to do things was the stop condition. My fault for being ignorant!

About passability of blocked tiles, I plan on leaving them passable as far as pathfinding goes. If best option is blocked, I'll have them take the second one so they don't wait in queue if the path is several tiles wide (which will be the case more often than not).

The other option to treat them as passable in a given number of turn sounds good too. But wouldn't that mean to use a "true" Dijkstra instead of a "simple" BFS?

I just finished a BFS implementation that uses a set of sources, a set of targets and supports one way tiles. Will test it a bit to see how it goes but here is the relevant (java) code just for the heck of showing something: http://pastebin.com/T63196Et

ps: I'll try Hydra Slayer right now. Already had a look to Hyperbolic Rogue and found it quite interesting.

[Z]

The other option to treat them as passable in a given number of turn sounds good too. But wouldn't that mean to use a "true" Dijkstra instead of a "simple" BFS?

Mostly yes (you could also use some kind of a hybrid approach where you use several queues for distances t, t+1, ..., t+5).

ps: I'll try Hydra Slayer right now. Already had a look to Hyperbolic Rogue and found it quite interesting.

Thanks!

[lulero]

The code pasted earlier has a bug, only checks for diagonal moves. "(dx != 0 && dy != 0)" should be "(dx != 0 || dy != 0)". It's fine other than that and It's way faster than I thought it would be, in 1000ms over 1500 iterations of randomly filling a 40x40 map with walls, basic and one-way tiles, picking 5 random sources, 5 random targets and computing. Now to add LOS.

Thank you Z, helped a ton. I think I'll stick around quite a bit

ps: Hydra Slayer is a pretty cool game Do you get to wield more than 2 weapons at some point?

EDIT:

Okay. A fun issue I had I'd like to relate here.

I had another bug with my code, not directly with the code posted earlier but with my Vector class.

To know when to stop computing I check if a set of targets is empty or not. Targets are x, y coordinates stored via a Vector class. The set is a HashSet<Vector>. But the remove operation didn't work and the algorithm computed all the map.

The reason wasn't that hard to find: my Vector class did override the "equals" method but not the "hashCode" one.

Lost no time and added a StringBuffer based one:

Code: [Select]

public int hashCode() {
StringBuffer result = new StringBuffer(x);
result.append(" "); // so 11, 1 and 1, 11 don't have same hash
result.append(y);
return result.toString().hashCode();
}
Worked as intented but the algorithm got 30% slower (a bit more than 1000 iterations per 1000 ms). Meaning that I'd have better performances WITHOUT a set of targets and by letting the algorithm compute the all map.

I then tried another hash:

Code: [Select]

public int hashCode() {
return x + y * 10000; // correct as long the width is <= 10000
}
Still worked as intented but was now 30% faster than the bugged version and twice faster than the previous working version (a bit more than 2100 iterations per 1000 ms). Felt good!

But out of curiosity I removed the target based test all together and let the algorithm compute the all map. It got only 5% slower (if not less) than the last version (a bit more than 2000 iterations per 1000 ms).

I guess it illustrates quite well what people keep telling me: don't bother with optimisations yet. I removed all target related stuff as it is as fast and easier to use.

[Z]

Thank you Z, helped a ton. I think I'll stick around quite a bit

ps: Hydra Slayer is a pretty cool game Do you get to wield more than 2 weapons at some point?

Nice to be helpful, and thanks! Yes, drink the Potion of Power Juice (and you should find one on the first level).