I'd really like an autoexplore feature. Just like Crawl's. Anyone any idea how to write one? Or will I need to RTFM and dig out the Crawl code and have a squizz there?
There was a thread on r.g.r.d. regarding Dijkstra Maps and how they can be used to facilitate an autoexplore feature (among some other applications).
To get a basic autoexplore going, find the nearest unexplored tile from the current location. This is where the Dijkstra Map comes in handy, but you can probably get away with a radial search + A* (or your pathfinding algorithm of choice) to get the nearest unexplored tile.
After you have the nearest tile, you "roll down" the Dijkstra Map or move across your calculated path, usually stopping when "something interesting" (ie a monster or item) enters your FOV.
Nolithius's suggestion makes sense, but there's an important difference between pure dijkstra and a radial search with a posterior run of A*: the first lets you find the closest unexplored tile in terms of distance traveled, while the second just finds the closest unexplored tile in the euclidean sense.
The problem with the second one is, for instance, if the closest unexplored tile is on the other side of a wall, and to get there you need to travel a lot -- when there may be another unexplored tile a bit further away, but the path to get there is much shorter. So sometimes the character may seem a bit dumb, choosing very long paths :P
Dijkstra doesn't have this problem. You can just run it from the player's position, assigning a path distance to each tile, and then just look for the unexplored tile with the lowest value. :)
The radial search suggestion should still use pathfinding to get the nearest unexplored tile, but, come to think about it, a Dijkstra Map of the whole map would be cheaper than a radial search + A* of the whole map!
6 comments:
There was a thread on r.g.r.d. regarding Dijkstra Maps and how they can be used to facilitate an autoexplore feature (among some other applications).
To get a basic autoexplore going, find the nearest unexplored tile from the current location. This is where the Dijkstra Map comes in handy, but you can probably get away with a radial search + A* (or your pathfinding algorithm of choice) to get the nearest unexplored tile.
After you have the nearest tile, you "roll down" the Dijkstra Map or move across your calculated path, usually stopping when "something interesting" (ie a monster or item) enters your FOV.
Cheers!
Ebyan "Nolithius" Alvarez-Buylla
http://www.nolithius.com
Nolithius's suggestion makes sense, but there's an important difference between pure dijkstra and a radial search with a posterior run of A*: the first lets you find the closest unexplored tile in terms of distance traveled, while the second just finds the closest unexplored tile in the euclidean sense.
The problem with the second one is, for instance, if the closest unexplored tile is on the other side of a wall, and to get there you need to travel a lot -- when there may be another unexplored tile a bit further away, but the path to get there is much shorter. So sometimes the character may seem a bit dumb, choosing very long paths :P
Dijkstra doesn't have this problem. You can just run it from the player's position, assigning a path distance to each tile, and then just look for the unexplored tile with the lowest value. :)
The radial search suggestion should still use pathfinding to get the nearest unexplored tile, but, come to think about it, a Dijkstra Map of the whole map would be cheaper than a radial search + A* of the whole map!
Cheers guys, these comments have been very helpful.
Here's the full article on Rogue Basin:
http://roguebasin.roguelikedevelopment.org/index.php?title=The_Incredible_Power_of_Dijkstra_Maps
Oooh, lovely, Pender. Ta muchly!
Post a Comment