Bay 12 Games Forum

After looking at the problem a year or two ago I came to the conclusion the problem with DF is not the lack of processing power of the computer it's the complexity of the algorithm used for path finding.

A* is a very blind algorithm which doesn't see farther than it's next step. A* typically calculate the whole path ahead of time and when a dynamic event happen it will hit the wall and then calculate the path again.

What I was thought in the University is that if a problem is too complicated to solve it should be divided up into smaller problems. The Divide and Conquer approach does help reduce the complexity of path finding in a DF like environment.  What I did is use a modified breadth first search to create rooms and also saved their access points . This way the first path is decided between rooms and then there are many sub-paths that are calculated along the way to traverse the rooms. I didn't implement an update method and abandoned the project. You can check the thread about it for details and simulator. 

I think that the current world generator kind of goes around the problem by reducing the depth of the world(z). I'm still not sure about this because I haven't played DF for a while. 

I was reading the pathfinding is A* every[citation needed] tick of a dwarf moving must evaluate 26[citation needed] positions.

I think that 26 came from path  step direction options and when he said tick he meant step. I also found that statement unusual.

If you can fly in DF and you are up in the air you got 9 path options above you,8 options at your level and 9 options bellow you. Because the complexity is approximately K^n or 26^n in that case A* can be extremely complicated.

BTW I saw your simulator. Does it use A* or JPS. Looking at that thread I might be able to push that JPS algorithm into my simulator. I still think a divide and conquer method with a dynamic update scheme can be optimal. I might go ahead and finish my implementation and then maybe add a 3rd dimension. 

How costly is your system to calculate your room nodes, as it sounds loosely like your overarching change is like mine: Reduce the size of the set of nodes that A* must iterate over.  I'd toyed around with a system to partition the world into rooms (I'd called them regions, but meh), but found the setup cost was too great to run well in real-time.  Moreso, are you able to get it to scale well into 3D pathing?

Room generation uses a modified breadth first search and it go through every open node on the map. I think generating it would be about 3 times more costly than no path penalty of A* because I'm considering 3 sets :overground, caves,HFS. It uses 2 points and a bit vector + room connection vector . I did the math once and it won't consume that much memory but for JS it's a little excessive( I also pushed some optimization to A* to reduce complexity because JS is slow).

Converting it to 3d isn't really a big deal. I think it goes through a coordinate array so all it needs to do is add a few points and another dimension . It's possible to keep it 2d by not allowing it to move on the Z axis and just find access point.

The thing is with this method is that you should build it once and then the update scheme takes over to maintain it. It only need to update when something is built or/dag. It can also update when finding those nodes not in room and merge them into the closest one.

But as I said I didn't touch the update scheme because it's not simple. I kinda abandoned the project at some point. My HDD also died  but I have a few backups.

I admit I didn't go through the whole thread but I did work on the subject in the path trying to get a working demo and I managed to get a few models done. I created a javascript simulator and posted it on this thread (in my sig too).

I've tested a few models :
waypoints - with path cache to every other waypoint. To get from A to B find closest waypoint to A , Wa and the closest waypoint to B Wb . then find a path A->Wa, use path Wa->Wb and then find a path Wb->B.

this saves time but you have to somehow select waypoint poistion and keep them updated when you change things because the cached path can change. the no path penalty can still be high.

-automatically placed waypoints - this is kind of a room placement . This uniformly places waypoints and find paths to their neighbors . this way you save a lot of short path and when changing an area you'll have less updating to do. it works similarly to the waypoint system.

- room based navigation - this is a divide a conquer method it's generally ideal and scalable . The idea is to scatter points like in automatically placed points but then create rooms out of them and save them somehow. The way the room are created is by using a modified breadth first search with many starting point and collision detection. When a collision happens  it's saved as an access point between rooms and it signifies a path between rooms .

To navigate point A to  B you  need to do is figure out which room , Ra,  point A is in.This is generally easily found mathematically and using elimination (it's generally fast). Then you have to find which room , Rb , B is in using the same process.  After finding the rooms you look for a path using A* on the room map from room Ra to room Rb this way you get a list of rooms. Now all you need to do is find a path from access point to access point.

This turn a potential k^(xa) to a *k^x problems . You can use a path cache but it's not really necessary. The room method visit less nodes on the map and have a clear dirrection unless an aimless A*. The many smaller A* also make it easier to deal with changing conditions. The main problem with this system is that I didn't figure out the update scheme for the rooms yet and didn't touch this project for a while.

you can try this maze . If you scroll down you can see the room I generated.The room pathing method I described above is done by pressing "advanced rooms no path cache ".  Because there are no update schemes then if you change the maze you have to click on "recreate wp rooms "(if I remember correctly) to regenerate the room. I recommend you use chrome because it's the fastest in JS.

A system like this can be implemented with periodic update or something like this but the update scheme isn't this complicated . All I have to do is figure out which room I'm in/near to update it but I didn't point my mind into it. the simple alternative is make all neighboring rooms fight over territory again. I know how to solve it but I haven't found the will to continue. I can go back to this if you guys really want  .

I still think that a key part of every pathfinding suggestion is always a working demo or clear methodology! Pathfinding is not a trivial subject and people who are involved in this should know a thing or two about writing code or the algorithms involved .

If you have an extra entrance you can use traffic designation to force your civilian dwarves to run to it if you designate the traffic zones before activating the alert. Here is a thread with an illustration. The picture is from my simulator but it works in game .

if they see the goblins it's probably too late.

My sumulator covers quite a few concepts but let me go over the complexity so you know what kind of slope you need to scale when pathfinding.

This little star represent the number of directions you can go without diagonal z movement.

\ | /
-U D-
/ | \


There are 10 directions to pick from. With diagonal movement there are 26 potential nodes. This means the growth is at a rate of about k/2 per step  of A* which is probably around O(min(Nmax,(k/2)^N )complexity  . As far as I checked there is a major penalty to visit a node . After numerous tests with my simulator it's not uncommon for A* to look at 50% of the accessible nodes before it finds a path. A* works well when there are no walls on its way. When there is no path to the target it would go through each and every accessible node.

I already implemented a hierarchical system which relies on a Breadth first search collider . It adds a bunch of evenly spaced nodes to a BFs queue and outputs a map of "visited nodes" with markers. it also figures out all the access points between rooms (I only save one) and this information is used to generate a "room graph". A path search consisting of a room to room search path search (on the edges) and then A* to the access point and then A* to the next access point until the destination is reached.

Raw results show that only 3-4%  (not much more than necessary) The smaller paths can be distributed between the frames and when there is no path the search fails with a minimal penalty rather than maximum.

My current code is JS but it can easily get converted to C. The algorithms are super basic . This project is currently on halt because of other distractions .

If you are brave you can try my  128X128 version with the map I tested ( I recommend google chrome, if you change the maze click "Recreate wp rooms "). My algorithm is called "advanced room no path cache" . My regular version is 32X32 or so and you can find examples on the thread in my signature.

Be aware I optimized the A* so it takes 100 thousand iterations instead of almost 200 million  . This made the difference between the room pathing . My A* still has almost 20 times more iterations than my algorithm because it's directly related to the number of nodes you visit during your search ( O(log n) insert  and O(1) search for min).

You can upgrade your horse to pull the cart up the slope but the longer you go the steeper the slope until you hit a wall and your FPS hit 0.

Quote from: lanceleoghauni on May 30, 2011, 05:23:36 pm

as handy as it is to modify, my programmer friends inform me that the Code for Dwarf Fortress is hell on computers. any fort that's above the starting wagon in size is going to have to deal with escalating computational needs of pathing, keeping track of every boulder on the map, and things in caves, caverns, etc. so as more dwarves show up and your fort expands, issues arise.

Or so I'm told.

You have an interesting way of writing. Your friend is correct though, DF requires quite a bit of processing power.

Yes, I already tested it. The  FPS is directly related to the CPU performance and not memory performance . I tested different CPU speeds with constant memory speed and got linear results when comparing FPS to CPU clock.

For now the best recommendation is get the fastest single core performance CPU  you can get and then overclock it. The current winner is Sandy Bridge and an economical choice would be 2500K .

Other than that I'm working on a  divide and conquer path finding suggestion that should fix a lot of problems  but I just need to do the "update scheme" . The problem with DF is that it gradually has to process  with more and more data.  There is also so much processing going on that we can't really pinpoint the main cause of the slow down. We can turn temperatures ,weather and flow off but we can't turn off pathfinding.

There is now a new dump destroyer tool in DFhack that can help us test the effect of number of items on FPS.   I just didn't get around to it  .

Quote from: Niseg on May 30, 2011, 03:18:27 am

This is a major trouble if a few dwarves are trapped between  two groups . They may osculate back and forth.

I really think you meant "oscillate" there 

:lol: fixed.
firefox spell check can't be trusted .