Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[catpaw]

Recently I had an idea about path finding I want to write down, before it gets ultimativly lost to my weak memory.

Okay. pathfinding is currently the single most framerate eater in DF beside hugh liquids in flow. How does it work currently, a dwarf is at position A, and needs to go to position B. The whole universe halts, the dwarf gets a mental represenation of the whole universe, and knows the ultimately most effecitve way to go from A to B. I think this does not only eat a lot CPU, its also unrealistic a dwarf suddendly knows about a door being closed miles away.

How could this alternatively work, without having dwarf run around like crazy lost roboters (like the old follow the left wall algorithmn that will get you out of almost every maze) ... Lets look how ants do it! They have no mental presentation of the whole world around them, yet their pathfinding works pretty well. They do it by dropping chemicals hints along the way for other ants. A ant going from the nest puts pretty weak signals on the floor, its  actually a dotted line. If it returns with food it will orient itself on its weak line and make a thick line over it for other ants as hints. They walk over as well making the line stronger..

How could this work with dwarves without making hugh memory requirements. Say a dwarf only sees a cube of 10 tiles in each direction. If the target is within the cube it will plot a path directly to target using the old algorithmn as long the path does not exceed the cube borders. If there isn't a direct path, or the target is out of the cube, it will plot the path taking him closest to the target (and additional corrected by dwarfes "pheromones" explained in a second). At the border he will plot a new cube... and so on. Unless there are some evil dead ends this should get a dwarf to his target with quite less CPU.

Now suppose a dwarf runs into a dead end. What does he do now? He drops a negative pheromone point. Like a dwarf repellant. So other dwarfes wont run into the same dead end.... So next time they plan the path in the 10 tile cube, they try to get as close as possilbe to the targer. However corrected by getting points that are further to dwarf repellant pheromones. If a dwarf makes a sucessfull path at the target he drops a positive pheronome point on the last cube he came from.. if the next dwarf gets close to a positive pheromone he drops one as well. So soon you willl have a decent path. With only a few memory bytes needed for the dwarf pheromone points.

There is come complication of course, since dwarves have more tasks to do than ants going outside of the nest. So while a craftdwarfs shop at the end of a large tunnel could be a dead end for most paths, its actually the right way if you want to go to this shop. So as solution every building needed its own pheromones... as as far I recall almost every dwarf path will always go from or to a building or stockpile. It takes some memory, but when you do this with pheromone points that signal at a radius, its not so bad IMHO. You don't need a per tile pheromone signal like ants do. This sure would be a memory explosion.

Also this can be optimized for when a dwarf has to go to a building with none pheromone points it will take a building near that target as reference, and orient itself on its path points. Also sometimes a dwarf should do a bit of variance on the path, so when sucessfulll he would find possible a shorter, making new signal pheromone points.

Well would need quite some simulation experiments to see how well it works really. I know in reality with ants it *does* work....

Just imagine for example a main route of the dwarves gets blocked, and all the dwarves stand running around in panic trying to find a new way

[Dae]

Tiles would have to keep track of every "pheromone amount" for every objective. It would work with ants because they have one or two types (food/danger), but with dwarves it would get quite heavy.

The idea takes less CPU power but eats more memory. I'm not sure it'd be a winning deal, but I don't know enough to judge.

Also, some already have had the idea before. After all, many discoveries were made observing nature.

[catpaw]

Tiles would have to keep track of every "pheromone amount" for every objective. It would work with ants because they have one or two types (food/danger), but with dwarves it would get quite heavy.

I thought I expliclitly mentioned/covered both problems above.... Did you read it or just skip it as soon you read pheomone?

[Dae]

Nope, i read it all (quite painfully because today was a tiring day for me). At first, I read but didn't catch the whole idea and had started to say the exact same thing as you, but then I re read it and erased what I was writing.

Oh, looks like I forgot the 2 sentences in question Anyway I let this as a sort of resume, which doesn't erase the fact that we sacrifice some memory for CPU usage.
And that i'm unsure wether it would be good. Considered some already have had the idea, it could be a reason why it isn't yet in the game. The other being Toady's unwillingess to rewrite the code.

[catpaw]

You are right it would require some more memory. However when "signposts" are used instead of adding pheromone level to every tile it should IMHO be only a few kilobytes in total...

Likely its just not been done already, because in the past there were always more pressing issues, or just the idea of the signposts wasn't yet there. I don't know 

[Draco18s]

The problem with a "yes/no" flag is that if the dwarf is trying to path to food and gets stuck in the bedrooms he's going to drop a "no" flag, despite his location being a perfectly valid path for some targets.

[catpaw]

The problem with a "yes/no" flag is that if the dwarf is trying to path to food and gets stuck in the bedrooms he's going to drop a "no" flag, despite his location being a perfectly valid path for some targets.

As mentioned in the very first post, every building would require its signposts. However I still do not think this is an enourmous memory explosion. How many buildings does a dwarffort have? 100? And now suppose the dwarves put for each building aprox 100 sign posts every know and then spread around the map. The pathing info would require aprox. And each sign posts takes 4 bytes data. X/Y/Z position and strength. This are 40kb in total... I think it would be acceptable....

[sir monko]

hm, i'm not sure if i get all this.

correct me if i'm wrong:

a different pheromone map would have to be created for every path. if there was a global pheromone map, the dwarves would follow any good-pheromone-trail leading in the general direction, even if the good pheromones came from a different dwarf seeking a different place. the pheromone-misled dwarf would then drop bad pheromones at soon he's stuck, driving away other dwarves seeking a place in the "poisoned" area.

so there would have to be a pheromone map for every path (altough you probably could use the same map for targets that are within sight of one another).

this would ...
1. require more memory (because a pheromone-map needs more memory than just the shortest path)
2. be less computationally intensive, because the path is computed step-by-step over many frames, instead of immediately - but also more ineffective for the dwarves, if the map changes (e.g. when a door closes)
3. make dwarves confused, if there is no pheromone trail yet

it probably would work if you'd divide the fortress into zones (e.g. rooms), and you had a different pheromone for every path from room to room, and walk the last step by line of sight ... but i'm not really sure.

[pavlov]

Ant Colony Optimization is a well known stochastic search heuristic. (google it). I've done some work with it. As with any random heuristic, it tends to settle on local optima. The problem with using such a heuristic is that it would not *guarantee* correct pathfinding, which would get really frustrating from a gameplay standpoint. 

[catpaw]

Sir Mondo, exactly it would require more memory in tradeoff to safed CPU. I'm just think done well it will use aprox 0.001 % of your systems main memory (thats still 2 Megabytes) and saving 50% of your CPU time.

@all, Also yes it definitivly would make dwarves less effective and the game a bit more harder. I consider this an improvement to the game, as having dwarves an inhumane precision for finding the correct path. Look at me, I drived for 2 years into work using a certain subway then a train. Only by accident I discovered that another subway and a different switchoverpoint is actually faster...

Should there be a "guarantee" that dwarves find the most optimal pathway, and should this pathfinding be instanous? I don't know.. I think rather not. So I don't know if it "would get really frustrating from a gameplay standpoint", or just add a little more challenge to it, so you rather tend to build fortress which have a few main passageways, as ones that are loaden with dead-ends large U-shapes and so.

Also mind in this model the dwarf can still foresee in a 20 by 20 cube... Something ants can't, so it might still easily more effective than ants, who have to rely on simpler tech..

[Silverionmox]

An overlooked resource in pathfinding is player planning. There should be rough pathfinding available for creatures outside and individuals etc., but the settlements themselves are highly planned and can be made subject to a traffic plan. Real life communities also have spontaneous traffic, "traffic habits" and planned traffic.

We already can do this to a certain extent, by marking an area to high traffic. Maybe that system should be expanded; that would definitely fit in the burrow arc. Dwarves would then be familiar within their own burrow (i.e. run pathfinding as usual), but use roadsigns in other burrows, if they are allowed there at all.
Roadsigns could be abstract: you'd place a roadsign on a certain spot, and other ones at other spots. Then link roadsign A to roadsign B, B to C, C to D and E, E to F, etc. The game would calculate the best path between the roadsigns and store it, periodically renewing it. The roadsigns themselves would then be labeled by the player. The dwarves then only need to pathfind in the network formed by the roadsigns. When arriving at the destination roadsign, or when their destination wasn't labeled in the network, they fall back on ordinary pathfinding.

[The-Moon]

Ive had a different idea for path finding for a while.

Maybe there can be someway toady can set it up so that we can pre-set degsinated paths around are forts.

Rather then what was said in the first post in this thread, Where the universe stops and the dwarf has to find a path to where he/she needs to go.

The player, "us" we set pre desinated "Roads" / "Paths" Through the fort.

If the dwarf needs to get to a certain location, rather then the program itself trying to find a path tile by tile. It reads the predesinated "Roads" / "Paths" which we set.

(im trying to be as clear as i can on this)

This system would work with the current system.

Such as the "Traffic zones" are already working and in place. These set traffic zones could be used to help the dwarfs get to where there going.

Instead of calculating and re calculating pathfinding.

The cpu/game makes a path using the "Traffic Zones" Rather then finding a path tile by tile.

A dwarf then doesnt have to look at the whole "Universe" it just has to follow the traffic paths we setup.

If theres a job at x=5 y=5 z=5

and the dwarf is at x=5 y=100 z=6

And theres a traffic zone set connection to where the dwarf needs to get to. Then it just needs to follow the path.

The game / cpu would have to of course assume that the paths we set are correct, and that there wont be any blockage getting from point A to B.

So as long as we setup correct traffic routes, the dwarfs will move fine.

There will be need of a internal checker to make sure the route the dwarf if trying to goto works. If the route doesnt work, "Give a message to the player letting the player know he effed up"

Well i think i kinda got my idea through.

Main theme of this, rather then checking 100 diffrent tiles, it mainly checks a single zone which we preset.

Being the traffic zones already in place.

Toady wouldnt have to change much code, i don't think, atleast not as much as revamping the whole path finding system.

If we set down traffic zones, rather then dwarfs looking all over the world to path find, it just follows the preset traffic zones.

Rather then using CPU logic, we use our own logic.

We could also be giving the option to preset paths OR.

For say a farmer, rather then repath finding from his bedroom, to the farm, to the dining room, to the bathrooms to where ever else that dwarf needs to go, once a path is found, the game should not forget about it.

Each dwarf should have his own store memory of where he or she needs to go. The quickest path it finds to its desitnations would be the one it uses.

If theres traffic zones setup, it trying to path find only by linking diffrent traffic zones together, and not having to complie every tile by its own.

Sorry for all the spelling mistakes, but its early and im not fixing them all even if there is a spell checker

Edit: Just to add on. The current path finding system would stay in place with myidea. But however, the current path finding system would be the last resort for a dwarf trying to get some wheres. The dwarf would first check the set traffic zones, before it trys to get to its destination with the current pathfinding system.

[sir monko]

@catpaw: it's true, perfect pathfinding is a little unrealistic ("somehow i just knew the path on the other side of the fort was blocked!").
i thought about your approach (and read about ACO), and it would work quite well if the pheromone trail is already there (altought i assume there had to be directed pheromones) - but it probably would leave your dwarf searching for hours to find a complex new path, if we assume he explores the path in dwarven-realtime (instead of pre-calculating it).

an unrelated question about the current pathfinding:
are paths cached at the moment, or recalculated every time? because if not, path caching could save a lot of cycles (and make the game just a bit more realistic).

path caching

pseudocode:
dwarf wants to go from x1,y1,z1 to x2,y2,z2

pick path:
1. is there a cached path from x1+-1,y1+-1,z1 to x2+-1,y2+-1,z2? (the +- because you probably could use the same path for adjacent tiles)
-> yes: pick it *
-> no: calculate a new one and put it in the cache
walking the picked path:
2. is the next tile of the path blocked?
-> yes: rate picked (blocked) path lower. if the rating drops below a certain treshold, remove it. goto "pick path" for a new one
-> no: walk on (goto 3)
3. are you there?
-> yes: rate the path higher
-> no: walk on (goto walking)

* if there are more available paths, choose the one with the best distance/rating ratio

garbage collection: from time to time purge low rated or very old caches from memory


pros:
+ reduces computational costs, because paths are not recalculated every time
+ makes dwarves use blocked paths for a time, until they know better (->the rating dropped too low)

contra:
+ caches = extra memory. not that much a problem, because you could limit the cache size. if cache is full, no new paths are cached
+ dwarves would ignore new and obvious paths until the old ones are purged from memory

hm ... i didn't test this, but i just wrote it down from memory, so there could be some severe problems i didn't spot. i'll probably write an implementation of this. on the other hand, i assume with a math background toady knows a lot more about pathfinding algorithms than i do.

edit: clarification

[catpaw]

Yes to all 3, indeed, I think the best thing would be some kind of hybrid.

Yes a dwarf trying to find a very complex path the first time could search for a long time. If the path is a real evil large maze, he might never get through it,  but just as well real humans would really get lost in a very complex maze. If the maze is smaller than the search cube, he would just run through it directly. IMHO it should first be encoraged not to build very complex mazes... and the player could make "hints" himself, little wooden sign arrows on the path telling the dwarves  "this way"...

I think the caching tradional complete path searches is a problem, since everytime you dig through a tile, or lock/unlock a door, raise/lower a bridge the complete cache would have to be deleted... which happens almost constantly at a DF:.. unless you life with the fact that a dwarf starts running a known path, altough it is blocked now, and only stop to recalculate a new path when hindered. Or if a new shortened way is opened up, the dwarves will continue to run the long cached patch, until it times out after a quite long time...

[Draco18s]

Or we could fall back to "follow right/left wall"

#########
#.......#
#.##.##.#
#.#.*.#.#
#.#####.#
#.......#
####.####
   #↑#
   #@#


Wait, no that'll never work, the dwarf here will never get that ore...