ToME Wiki
Disclaimer
- This area has little to do with ToME besides the fact that it's rogue-like oriented. All programs linked here are not garanteed to be virus free altho my virus scanner didn't find any. Use them at your own risk.
Path Finding
Aural
Algorithm Theory:
- Cast an 'aura' from the initial position to the destination noting the distance it covered then trace back to it using the shortest path.
Meta Code:
Aura: point = start for each non-calculated direction from point assign it a value higher than the value at point recursive for the point at the direction found Trace Back: point = destination while point is not start Find the lowest value from the adjacent points if more than one is found follow the absolute direction to start point = point with the lowest value
Example:
Aura Path +----------+ +----------+ +----------+ | # | |4345678#67| | 567 # | | # # | |3234#89#56| | 4#8 # | | # # | |2123#90#45| | 123#9 # | | @ # | |1@12#01234| | @ #0 | | # * | |2123#123*5| | #123* | +----------+ +----------+ +----------+
Good:
- Small maps are the best for this kind of path finding;
- Tight corridors and rooms also make the calculation way fast since those are ignored;
- Can path find a labirint easily
- Works on any kind of maps
- Works great with terrains that cost more to travel, just add the cost to the number assigned to each step and it will simply find the fastest (cheapest) way there.
Bad:
- Open terrain takes a long time to calculate, but you can do a directional aura if you know there wont be much blocking the path;
- Time to calculate an area is squared;
Aural Path finding chatter
ReenenLaurie:Would it be longer (in a worst case scenario) to do directional 'guessing'? I assume a little longer but on average you would save. Otherwise look at blockades... and remember the points surrounding it (working back from target might help?) Then recurse your algorithm and add the values to see which one is shorter. However you might at times become satisfied without *knowing* you have the shortest way.
SoulWynd: In the worst case scenario, yes. Depending on your map structure, you will be better of with a vectorial path finding algorithm (I should lay it down here later). On really open terrains you could simply move towards the absolute direction to the target and give it one or two lateral steps so if you get stuck you can find a way out. Actualy, this is how tome does it and with any kind of esp you get to see how they get stuck in corners. The 'aural' path finding algorithm works great for small maps. For an example, if you were to draw a 80*20 map block by block it would take you 1600 steps. I'm using that size on my demo and if you run the v0.4 you will notice that it doesn't take that much to find a path with these conditions, so it's faster than drawing the map on the console.
ReenenLaurie: Yes, the tome AI is not great (would be great if it can be improved). But having a whole pit of monsters trying to find you could be a bit of a strain on a PC? (though I assume the PC's nowadays have no problem, but we don't really want to exclude those who still runs < pentiums.
SoulWynd: There's a small variation of that algorithm that's meant for several npcs to track down the player. You cast a single aura from the player towards the whole map (or the most distant npc who will make use of it) then each npc traces back towards the lowest value, which aint cpu intensive at all (takes the same cpu as moving towards the player without any algorithm). You can limit the aura casting to happen once every 10 turns. They still can follow the player's old location and at worst, the player will be 10 steps away. If the npc has visual contact with the player it will follow the normal 'move towards the player' dumb ai. This is actualy great if you want to make use of smell/sound tracking since the npcs will not follow an exact location, but a location where the player was a while ago.
Demo
http://www.geocities.com/kudex/pfind.zip (w32 v0.1) - 45Kb
- It's not free of bugs and you might find some strange paths mostly because I still haven't made it step back if needed. Note that this demo only considers the four cardinal directions.
http://www.geocities.com/kudex/pfind02.zip (w32 v0.2) - 44Kb
- Free of bugs (seriously) and if a path is possible, it's found no matter what. It's also faster and OO now. No need to step back either, have fun watching it. Next version should have a diferent map generation and some commands to fiddle with.
http://www.geocities.com/kudex/pfind03.zip (w32 v0.3) - 44Kb
- Added a couple commands, so you don't have to run the program over and over if you want to see it doing it's job. Should help with lazy people who don't want to use the prompt :p
http://www.geocities.com/kudex/pfind04.zip (w32 v0.4) - 44Kb
- Added a couple common cave generators.
- Symbols:
- @ = Origin
- * = Destination
- # = Wall
- . = Aura
- o = Path
General Chatter
NeilStevens: I'm glad to see this sort of stuff appearing on the wiki. With all the hassle that the very restrictive ToME/Angband/Moria license gives us, I'd love to see a new game released under an unrestrictive license born here. One that learns from ToME without repeating its mistakes.
What langauge do you write in? I urge you to avoid C-derived languages because they are poor for string handling.
SoulWynd: Yes, it would be nice. I will be linking to my programs and copying my algorithms here, so they're made public (considering tome has a good public). Oh, I hate licenses and copyrights, I've had trouble with it before when people decided to copyright my own material. They really lack a sense of reality. Anyway, that one is programmed in D and I will be converting all I have to D as soon as I can. D is great for string handling, it has all kinds of improvements towards it and if you think things are getting too complicated you can simply use the string module which has most functions you will ever need. While on C you need to strcpy in D you only need to string_c = string_a + string_b + "D Rocks."; ... If you want to add something you just go like string_a ~= "What you want to add."; ... And that is while working with char arrays, string variables are even more complex. You can find D here:
NeilStevens: I'd heard of D for a long time. I'm surprised that I'm actually seeing someone use it, though. ToME basically satisfies my interest in writing such a game, but if that changes I'll be writing mine in Ruby.