Print

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

[thijser]

This is basically about a new way to get the pathfinder to work.

Currently the pathfinder will calculate a new path each time a dwarf wants to go from one place to another.
This is inneffiecent and not very realistic.
I think we should chance it in this way: the first time a dwarf has to go to a certain stockpile from a certain workshop and back he searches for a path he does this manually so he walks in the general dirrection and with a bit of randomness he will hopefully find a way. This way is then written down and saved. If this dwarf talks to another dwarf there is a chance they mention this path and that they will share their pathing information. If this is done both dwarfes will know eachother paths and will use them. Dwarfs who aren't doing anything can be set to explore new roads between workshops where they have tasks enabled.

The advantages would be:
1 A higher FPS
2 A more realistic system (dwarfs don't magically know that a certain road will work)

disavantages
1 Need to be coded
2 Will make the start of a fort even more difficult

Addinally a system could be added that makes them try to find a path that crosses their old path if their path is blocked.

[TheyTarget]

This does seem more realistic, and would probably make people kill themselves with frustration. Though I think it would be something toady would want to use. And I think it would work awesome with dwarfs in adventure mode. Where you tell them something, and they wonder around. Though, while they dont know the path, they should at least know the general location so they dont get horribly lost.

[thijser]

For general directions we could let them use a system simulair to the current pathfinding system.

[devek]

Hate to say this, but your solution would still be slow.

[Soralin]

Yeah, the problem with this is handling anything beyond the simplest of situations.  Say for example you have a dwarf in a room, with a single door on the west side of the room, and they want to go to a location which is off to the east.  What will be the first thing that they do?  Run into the east wall.  So, you code some workaround to get around walls, expand your vision a bit, look to the north or the south, to see if you can find a way around the wall.  If you can't do that, then you may have to start checking back in the opposite direction, until you find the door out.  You can then check north or south, and eventually find a passageway that leads in the direction of your goal.  And the dwarf can then repeat this process, always preferring to move toward the goal, and if they can't, checking passageways moving in the general direction of their goal, and nearest their goal first, before going back and checking others, if that fails.

Which sounds great and all, until you realize that what I've described above is essentially similar to A* search.  In other words, what the pathfinding is already doing in it's mind, instead of moving the dwarf around.    And doing the same set of calculations, just spread out over a longer span of time, rather than all at once, isn't really going to end up helping.

[blizzerd]

how is pathfinding done atm? maybe someone could write it down in pseudo code or explain clearly step by step how the code works on pathfinding? i bet the community can optimise its workings

[Soralin]

I'm not sure if it's been answered, although it's likely A*, or that's what everyone seems to think it is, it's simple to program, fast for pathfinding, and finds the shortest path, so it gets used a lot, see: http://en.wikipedia.org/wiki/A*

Basically you look at all the surrounding tiles(possible direction to move in), toss them into a sorted list, with the the ones that have the lowest (distance from starting point + minimum estimated remaining distance to destination(i.e. straight line distance)) at the top of the list, and the rest in sorted order below.  Along with a link back to the tile that they just came from, the starting tile in this case.  Then you remove the one off of the top of the list, and add all of it's neighboring tiles to the queue, in order, with links pointing back to that tile (excluding ones that have already been added before).  And so on and so forth, taking the one off of the top of the list and adding it's neighbors, until you eventually reach your goal, at which point you can follow the chain of links in a straight line back to your starting point and you have your path.  It works quite well, because it's always searching in the direction of the goal first, and when it backs up, it's always checking the closest paths, and the ones that move toward the destination and such first.  And the path it finds is the shortest path to reach that destination, given a couple of conditions, like that your minimum estimated distance is actually a minimum, and that there aren't negative costs where you can get somewhere faster by traveling around in a circle multiple times or silly stuff like that.

There have been a number of suggestions from the community on various ways to improve on it, by myself even: Pathfinding by rectangles

There was also a big thread on improving pathfinding a while back: Anouncing The PathFinder Project  Although I'm not sure how much actually got done there.

[thijser]

Yeah, the problem with this is handling anything beyond the simplest of situations.  Say for example you have a dwarf in a room, with a single door on the west side of the room, and they want to go to a location which is off to the east.  What will be the first thing that they do?  Run into the east wall.  So, you code some workaround to get around walls, expand your vision a bit, look to the north or the south, to see if you can find a way around the wall.  If you can't do that, then you may have to start checking back in the opposite direction, until you find the door out.  You can then check north or south, and eventually find a passageway that leads in the direction of your goal.  And the dwarf can then repeat this process, always preferring to move toward the goal, and if they can't, checking passageways moving in the general direction of their goal, and nearest their goal first, before going back and checking others, if that fails.

Which sounds great and all, until you realize that what I've described above is essentially similar to A* search.  In other words, what the pathfinding is already doing in it's mind, instead of moving the dwarf around.    And doing the same set of calculations, just spread out over a longer span of time, rather than all at once, isn't really going to end up helping.

except that this path is now saved and the dwarf will have it in it's memory so that it can be recalled at any moment.

[aepurniet]

(computer) memory usage wise this would be a non starter right now.  storing every path, for every dwarf, would be impossible.  also this has the disadvantage of being non reactive to changes in the map.  if you use the rectangle approach described in the post above, you could store some common subpaths, and have those be exchanged in conversation though.  i totally see some dwarves taking the 'long' route, while the lazy good for nothing dwarves that party all the time taking the most direct route everywhere.  dont see how this adds to gameplay.  it would make the game more FUN though, as your busiest dwarves still take dumb paths during seiges that lead to their slaughter.

the old crappy paths would essentially be mental diseases that spread infecting younger dwarves, making them walk obtuse paths.

[Soralin]

except that this path is now saved and the dwarf will have it in it's memory so that it can be recalled at any moment.

And you can do that with A* pathfinding as well, just as easily, if not more so, it's been brought up before as path caching.  And you can do some things to counter the problems aepurniet brings up, like removing paths them from the cache when there's an update to the map that could make them out of date or just removing them after a period of time or such, trading off speed for accuracy.  Which always has to be done in any case, or everyone will just attempt to take the same path they took the first time, no matter what changes, like a new passageway opening up, or a wall being built in their way, or so on.

But there can also be problems to that, say for example you have a path cached from a workshop to a tile in a stockpile, and then a dwarf wants to find a path from the workshop to the same stockpile, just one tile over.  If you just looked for a path in the cache directly there, you wouldn't find anything, and would have to find a new path.  Or, if you wanted to try and use partial path caching or something like that, how do you check paths in the cache to see if they can be used to reach your destination?  I mean, you could check every path that could potentially be used, and check the pathfinding from you to it's starting point, and from it's ending point to your destination, or to another cached path, or so on.  But if you're not careful with it, that can quickly end up taking more processing power than just finding the path directly would take.

Or, you can set up a system in which pathing, and path caching is much easier, because it can look at larger areas, rather than just one tile at a time.  For example, with the pathfinding suggestion I gave above, a cached path could work for any dwarf going from the same general area to another same general area, like from anywhere in a dining room to anywhere in a food stockpile, or so on, because it works in large sections, and only needs to think about the connections between them.  Or hierarchical pathfinding, which splits the map up into larger grids, and could work roughly the same way.  Although cached paths in those instances might not end up perfect, since you can be starting at some point within that starting area, but they would be close, and the pathfinding in general would be much faster, even without the caching.

[devek]

You're still pathing over an arbitrary graph so you lose.

[Kadath]

How about this:
When a dwarf enters a tile, that tile is slightly increased in priority for the pathfinder - after a while, tiles that are never traveled won't be calculated anymore.

[Xzalander]

How about this:
When a dwarf enters a tile, that tile is slightly increased in priority for the pathfinder - after a while, tiles that are never traveled won't be calculated anymore.

Ideal really..

[thijser]

How about this:
When a dwarf enters a tile, that tile is slightly increased in priority for the pathfinder - after a while, tiles that are never traveled won't be calculated anymore.

That might work but maybe adding a signpost that would make dwarf try to path in that dirrection aswell so that your dwarfs won't constantly be taking the same weird path because that's where the alcohol storage is so that will be where the magma forges are aswell.

[jei]

This is basically about a new way to get the pathfinder to work.

Currently the pathfinder will calculate a new path each time a dwarf wants to go from one place to another.
This is inneffiecent and not very realistic.
The advantages would be:
1 A higher FPS

I think it is very clear to everyone playing the game for any longer period of time, by now, that this is very much needed and necessary,
but it is nearly useless for us to speculate how to do things better because we don't know the specifics of how things are done now.

Also this method of yours would have a major impact on the AI. I don't think blind bumping around and learning ways is going to work or would be annoyingly slow each time a new path would need to be learned.

A better alternative might be more efficient caching of the calculations, elimination of useless work and not repeating the same work, time and again, when possible. Maybe splitting the path calculations and dumbing down the paths for animals and random clowns that don't have a path available to them the first couple of times they try and triggering new path checks to happen only when some construction, cave-ins or or dig work (or floodgate operations) are to be done in the levels that are accessible to them. Until such time they should just randomly wander around and not allocate heavy path calculations.

Also a lot of the work could probably be offloaded to any second CPU of the computer, bringing instant relief to many.

I was told another problem might be rock-junk that require constant calculations. These should probably start to be limited heavily, depending what takes most of the CPU now. Maybe forbid dug out rocks by default and exclude them out of any path calculations, perhaps limiting permitted rocks by default to permitted types of minerals and areas designated as sources for rock and not consider each and every rock every time a dwarf needs something.

Something needs to be done or for most the game turns unplayable with a bit of time. At least to me, this has not depended on the size of the game area as much as it has on the in-game years I've played the game. Killing all the pets and wild life will also get one only so far. It is no panacea. Maybe mass destruction of loose rock would be an ease, but even this is stupid if it's to be required just to be able to play the game at a decent FPS.