Show Posts
1
Programming / Question about pathfinding in a particular context
« on: December 17, 2011, 03:48:04 PM »
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:
Also relevant are the possible tile types:
IMO why choose Djikstra over A*:
IMO why choose A* over Djikstra:
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?
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?