Bay 12 Games Forum

I used to use them as target practice... but i got lazy - I throw them into an 8~ z level pit - it does the trick. I also use that pit to take care of the growing cat population. I got an atom smasher at the bottom to take care of the remains and miasma.

Multi-core discussion again  . I don't think it should be considered unless you do a GPU offloading (300+cores). And if you want a fast CPU a Ga-As processor can reach about 50GHz and a Si-Ge processor was made recently which ran at 350GHz on air and 500GHz on liquid nitrogen.

If path finding is the problem that causes the degradation of  FPS  my room system (the no cache button) can fix it easily. Theoretically you can run a 16X16 embark with same FPS as 1X1 with a room based pathfinding but... there are other things like flows and temperatures - I don't know how they work...

The best way to improve performance is to improve algorithms but because we aren't in control of that just get the fastest cpu (single core performance) and overclock it. (2500k/2600k are the winners today).

Well, its true you don't have to totally regenerate with any system. When someone digs out a room you just add to the nodes/mesh either way and optimizing it during spare cpu time.

What sucks (for any method)is when someone locks a door, currently you can feel DF hang for a second recalculating its pathfinding data.

I don't think it would hang for a second. With a non-caching method all you need to keep track of is weather a "room" is accessible or not. You should also consider the fact that the UI and user are significantly  slower than the back-end and CPU.  When you make a change you might want to go through  path validation but that's pretty quick on room paths(no guesswork either),  or let everyone hit the wall(like they do now.

 I think A* should be modified farther for this mode - it should consider the room shape and it's destination - it should consider nodes in other rooms to be blocked.  I can do that currently by quitting prematurely when it  start considering nodes that are significantly away from the target (it go to the closest ones first). It's too general and costly to do it this way.

Either way, your method will work and it is going in the right direction now. With a mesh or nodes, you're actually working with a proper graph now and this is where things actually improve. Feel free to burn as much cpu building/maintining your graph, in the end it is cheaper than traversing a suboptimal one.

It's not a matter of "proper" or not the current map is fine as a graph the problem is that it's really big and  too complicated. I've read in a book google scaned that they don't recommend using pure A* on "boards" larger than 60X60. What DF has in a 4X4 embark is a graph 192X192X100    or 3.7~ million nodes .  I'm not sure how Toady implemented his A* but if there is a dead end and you can  access to 1/10 of those nodes you are pushing 370000 nodes into a queue before you figure out it's a dead end.

The overlaying map model just leads A* to the right direction this way it doesn't get overly confused and kill your CPU. It also divide the A* of  a long path to many small A*s for short paths which spreads the load a little.

I'm happy to inform everyone I just wrote a non path caching 2 layer A* (it's called " advanced  rooms no path cache")  that simplify pathfinding cases to its most trivial cases. Room shapes and handling  need a lot of  work but it's not as important because it works with any shape room. It's also a very simple program. the only complexity in it is A* and it's changes (not that bad either)

In my early example A* finds a  110 length path visiting 813 nodes (it's really lost). My algorithm finds it in 203 this may sound bad compared to path caching but the big difference is that it finds to finding 13+1 paths with an  average length of about 8 steps . The "destination unreachable"  penalty is also really low about 16 node visits ( I got 16 rooms ).

The way it works is simple : it uses BFS collider to find rooms and saves their shape (square + bit vector). The collider also save the first collision point of the path ( I think I need to move it but it's not important) . The info about the destination id now also saves the collision point which means the room know at what coordinate is closest to the other room.
After building all the rooms all it does to get from S to D is find the path between the rooms

S and D exist in and then it pushes S to the output_path. There is a loop that looks for a path from the end of the   output_path to the next room's access point then it concatenate the path to  the output_path but it slice the last element for it.

With this system all a mob need to do is save the overlaying path and then calculate paths as it go from room to room . It's so trivial it runs as fast as the room pather with the caching.

Be aware though - you we have to recreate rooms whenever you change the maze. As I said I'm not updating the room structure when the maze is changed yet. It may still work if you keep access points between rooms.

you can check other examples it should work you may get unusual results because I just save the first access point and doesn't consider others in any way.

EDIT: I'm marking the subpathes now with 'O'
you can see it here

Here's an example where the current room algorithm apparently fails to find any path at all, in case that's helpful.

here is a fixed link to that maze . I can't seem to access my old site(I should get a domain name...) and I'm not sure it's updated .

I agree that the room based algorithm needs work. The advanced version is off by a mile.I think i know why that happens - the heuristic for room base search is on the room map which means it doesn't evaluate the distance correctly.

EDIT: I figured it out it's because of the use of path caching from the center of rooms .  I'll add a search that doesn't use path caching . I might ad an access point parameter to the edges array and go for those. I'm also considering moving the central points or splitting very large rooms




I  also  another problem with  A* case for rooms  in this maze it doesn't find a path  to the destination because it only look in the "board" while the edges between rooms are not related to their location on the "board".

I'll fix both problems by tommorow. Thanx for the feedback! 

One thought on the floor(sqrt(x^2,y^2)), have you considered a lookup table? for the small area you have, and that it's all integer input and result, 1kb (32x32xa byte) of memory might (might, needs testing) be faster than those operations.

Heuristic performance is not a critical part of this simulation due to the fact JS is inherently slow . It might help if I run performance test by telling it to find path x times for example.  What i try to optimize are the node visits which is affected by the distance to the destination and the complexity of the maze(how well it fools A*).

The idea with overlaying room is to reduce both the distances and the edges. It also make a complex maze fairly trivial as you can see on the bottom.

It's not that bad even with 32 bit per block the weighted A* might cause it some trouble but the use of bit vectors means it should run pretty fast and should fit in cache easily enough.

Anyways I managed to create my first room navigation search based on the BFS-Collider rooms . The way I save the dimensions  isn't optimal(x,y,dx,dy,width,height,mask[8]). I should start node exchange soon.  My search function is fairly stupid it goes through all the rooms(it doesn't have to it can guess pretty well), find the start and end room , build a paths to their central points and then find the path between rooms( I need to fix that heuristic).

I think room pathing should cover anything the update scheme shouldn't be bad. if you dig a square you need to check which box it's in ,update bit vector or expand the box if needed. I guess I'll do it one step at a time  .

You hit the nail on the head. Before Toady did DF, he was paid money to know math. It is kind of like going up to a race care driver and telling them they could take faster turns if they focused out for their weight distribution, it is kind of pretentious.

I'm not sure what Toady's background  but if someone wants to suggest a better pathfinding  algorithm they better know something in the field of computer science, discrete mathematics etc and be able to offer code or well outlined implementation.

I had no AI or pathfinding background other than having a CS degree and being able to code my way out of a plastic bag.  I found it interesting so I went and learn a little about  the subject.  After trying stuff myself I can make suggestions that work. I've been trying to convert some of the ideas on this thread into code. This also gave me another opportunity to experiment with JS and CSS etc.

Don't get me wrong though, there is nothing wrong with pathfinding improvements. It would be nice if when a dwarf constructed a wall, that it did it from the closest tile instead of always building from one side, it would be nice if it grabbed the stone that was close or on the way, it would be nice if we had multi-tile monsters, etc. Toady isn't sitting around trying to figure out how to do it, he is simply busy working on other things(like hill dwarfs, taverns, and cities!). We will get those things when they get to the top of the enormous list of things left to do.

The issue with dwarfs always building from top can  easily solved with some weighing and heuristics I don't think that it's such a major issue anyways. Just open the circus if you want FPS to drop and there aren't that many clowns in there but they certainly kill fps in their marketing campaign . they got big k and big N to reach their customers and they can reach more nodes than anyone else.

It is also logical that you could improve FPS by improving any piece of code, but premature optimization is a killer waste of time. The truth is, exponential slowdowns in DF are the result of bugs. The most useful thing the user can do is upload saves before and after such slowdowns occur. Furthermore it is difficult sometimes figuring out how to properly write a piece of code when you don't know what it is going to do, DF is a huge work in progress.

For example, let me show you a graphed view of the function that determines what an object is when you look at it.

Spoiler (click to show/hide)

There is so much waste in that I could cut away with a few key strokes, but why bother? Right now it is flexible enough to add all sorts of cool new features and items to the game. The biggest performance gains are not possible to implement until you actually know what you are trying to do.

That looks like a call stack or something - look kinda blurry. I admit I have no Idea what's killing my CPU. If it's the dwarfs looking for items, thiefs looking for stuff to steal or 200 cats looking for who know what. All I know is that more Mobs = less fps which probably translate to pathfinding.  I know that turning off temperatures boosts FPS I haven't checked fluids flow. Maybe its the magma?!

This is why I like path finding optimization approach and you don't really have  to add much . It's a classic divide and conquer approach that every CS major should knows by heart .

My room scheme should offer great improvement and it has another advantage - you can do it over and over again to simplify the map farther.

Unfortunately my current [http://niseg.moshela.com/test_maze.html?maze=v05GAk0YzlSI1LhfmxHFkSulWNLiARSGSQJhJDJIZJAZJDJIZJAZJ9_x-UuNFMZC9HuMTTdIjx4hYifIzEWzFYj39cmIIvOSxJsRWJOjzJiAxKbpUADSixCQIxJEYkhkkBkkMkhkABkkAMhkkA]favorite maze [/url]doesn't show splitting it up too well :

0-1-2 3
|    /|
4 5-6 7
| |   |
8 9-A B
|     |
C-D-E-F


This is basically a strait line
2-1-0-4-8-C-D-E-F-B-7-3-6-5-9-A

If you look at it structurally you can divide it into the center region, the top left-region , the bottom region and top-right region

The problem with A* is that it can't see it as a strait line and it have to hit every wall in the general direction of  the target. If a dwarf wants  to look for an item and it's listed at 63,63 when the dwarf is at 1,1  it usually take 100-300 node traversal to get to the target  but if he know he's in room 0 and the item is in room F it takes 9 . That's only about 10-30 times faster . As the maze get larger and more complicated the gains get bigger and all you need to do is some pre-processing and maintaining the overlaying structure. The memory costs shouldn't be that big (my js program might be a hog but it doesn't have to be).


I do agree that profiling would get us far but I got no clue how to do it on someone else's code on a windows platform.  I am thinking of running some more tests with max fps to see the true effect of pathfinding . I'm not sure what else to concentrate on maybe item search  .... i'll do that after the path finding project  .

one thing i have noticed about the A* approach (and probably most others) is the exponential increase in calculations over greater distance (due to the exponential increase in path options, most of which are redundant and unnecessary)

The complexity is about min((k/2)^N ,Nmax) which means node explosion . A* is also fooled by dead ends . there are a few examples for this

there are two suggestions i have. one would help a lot for pathing in a fortress. by breaking the fortress down into rooms separated by doors, you could simplify the code by using a macroscopic version to calculate what rooms you need to go to, and a microscopic one for pathing through each room. even if it needs to preform the same amount of pathing checks it won't have to do them all at once, only once every time the object enters the room, spreading the lag more evenly. this also means numerous shorter distances instead of one long one minimizing the exponential growth in possibilities ( i know it is better then exponential but the algorithm hates distance. you could even use memory to store the path from one end of the room to the other (though this would have to be compiled and called on when needed because RAM is taxed as it is (i think))

I think that's around page 15-17 or so of this thread.

I did implement an arbitrary room generation with patch caching between them . you'll see it in the picture above your post(it's spoilered to save space). the cyan on gray Rs are the rooms and the path between them is shown in light gray. The path itself is cyan background floors.


here is a condensed version of my code with dest-path part choped (same as spath after reseting variable) but it's still pretty big though what it does is simple.

first thing it tries to find a path to the room closest to it but it limits its search to nodes 16 or less away. then if it fails it tries again with longer distance . (the complexity of the second search is much larger than the first). if it still fails it assumes that it's by a wall and the best candidate rooms are the ones not connected to it's closest room. if it fails to find a path to those rooms it gives up.

after it's done with path (xs,ys)->R(wprxs,wprys) it will then find the  path R(wprxd,wpryd) -> (xd,yd) the same way (this part is choped). then it look for a path from start room to end room on the room "maze" which is  a 4X4 size (atm) and if it doesn't find a path - it returns empty path. otherwise it goes and concatenate spath to all the subpaths of the room path (not necessary to save path  - short distance A* is usually pretty fast).

As I said before the begining of the function that got to do with room selection needs a lot of work because waypoint based rooms are just terrible in terms of finding "where you are"  . The last part is pretty simple once you find the connections.

Edit1:

After playing with the code a little I added a BFS  collider  to find edges between rooms - sure it goes through every node in the maze but it finds all the connections between rooms and their shape in one pass . All I need to do now is to add  the info to room data structure , then I'll need  to create a better navigation function then a room update scheme ... lots of work . I still need to fix the bfs limits scheme so it know when to update the depth counter correctly .

here is how it looks like - it puts the output at the bottom whenever updating rooms: