Bay 12 Games Forum

AMD used to have a timer problem I thought they fixed it by now. I did a search and it's related to RDTSC oppcode. I don't think it should matter. The symptoms  for this is games running too fast.

that ant farm reminds me of path caching which has a big penelty when a path to the destination doesn't exist. you also need a path smoother but that is not to bad in terms of complexity.

my room spliting is a beter choise but i need to figure out an update scheme. you can practicaly regenerate all of them every 1000 frames and be fine. that is not optimal though.

it reduces complexity,  split the path and has a low penalty.  the room system can also help finding the closest item.

it has. room for improvment but. it works. well as is.

posted from a PDA sorry for the bad English ...

Maybe you should suggest adding "line drawing"  in designation menu in addition to  filled rectangles . I've added line drawing to my simulator before adding filled and empty rectangles. I admit coding line drawing isn't as intuitive as rectangle but there is plenty of code on the web for that .

Here is a simple ambush setup done with traffic zone(image).

It works on the simulator I'm not sure about the game. You may want to make sure the dwarves don't look at the goblins and if they do they might take the path around rather than the direct path below . you may be able to improve on it to work with two squads but I admit it's hard to create a battle plan by drawing traffic zones over and over.

Anyway, making DF multithreading at the end... won't work (very well) multithreading has to be in the core design

After writing code in a multi-threading  environment for a long time I can generally say  your statement is  not true. What's true is that you should know what you are doing and what you are trying to achieve . Without going into details you can generally convert any for loop that process independent data  into a work queue scheduler . 

To gain entry, you must start a new forum thread suggesting mutli-threading, improved pathfinding, multiplayer, and/or open source code.

I suggest that people that open a suggestion without giving a clear methodology should donate 10$ to Toady to  figure it out.

The pathfinding suggestions are all in one thread .There is a lot  progress in the in the clear methodology area  . I implemented a demo of 2 of the suggestions . I know  room pathing is half done  but it simplify the problem by a factor of 10 and no path penalty runs at best case time instead of worst case every time.

Toady made DF run a whole lot faster by using coding magic. Also making the game multi-threaded doesn't fix the game's problem, it just hides the symptoms for the time being.

 I haven't noticed much of a performance difference (maybe because my 25% overclock stopped being stable - I blame my cats) . We are totally in the dark in the benchmarking field because it's hard to points out the performance killer because there are more than one. I think it got to do with how data is organized .

When trying to solve a complex computer science problem faster you generally have 2 approaches:
1. getting a more powerful computing engine and adapting your code to work with it.
2. simplifying the problem

The approach you took is approach 1. Many people think this approach is the best course of action but in my opinion it's not. There is a limit to how fast you can make the program run using multi-core and multi-threading and in the age of mobile computing pushing the CPU to the edge is not the answer.

The best approach is to simplify the problem  and the most common approach is divide and conquer .  If you replace the problem with a many  smaller problem you'll generally find a more efficient solution.

I had this problem with my path finding simulator. The original A* I used did 3 linear searches  (O(N)), 1 to find best node, and two to check if the node is in the open or closed set . I replaced the "push" (O(1)) to "insert in order" (O(log N) ) which converted the "search for minimum" from O(N) to O(1). This made it run about 1000 times faster. with 128X128 map max(N)=16384.those 3 linear searchs take about 3*(N(N+1)/2) that means max complexity is 268.5 million iterations. This is reduced to 16384 insert in order which is much less than NlogN = 0.229 million iterations.

Now here is the problem. If you have all those optimizations in and I'm guessing Toady got them all. The problem is still too complicated when you have an max(N) = ~1 million. You go through max(N) every time 19*1million is still a lot . For this reason I generated an overlaying graph of "rooms"  which takes about max(N) iterations . It generates room , how they are connected and the access point (I pick the first - not optimal).  This reduces the  "path doesn't exist " penalty from  the number of nodes to the number of rooms. Instead of looking at the "big world"  the pathfinding  creature only looks at the road they picked . Most of the paths also become  trivial where A* performs best case almost every time.  This is also less memory intensive should have very good cache performance. Unfortunately it needs more work  because I didn't even start room updates yet .

I admit pathfinding isn't the only thing that's slowing DF down but I can work on 1 suggestion at a time . I think that performance issues are a pressing concern but  I'm hoping that showing a working alternative would make Toady's life easier when he finds the time to work on them.

It is possible that an enemy gets a chokehold on such soldier and he is dead then. I had it.

That's one of my favorite adventure mode tactic - learned it from a play along. Choke the guy and administer fun. Big fights = hammer to the head smaller ones - axe all the limbs just in case. I once thought I could train my weapon skill by hitting unconscious enemies but it didn't seem to work . I think a better tactic would be to cut off their arms or legs .

A tend to agree you shouldn't rely on 1 guy even if he can chop off armies . There is always a chance someone hit him in the head with a silver hammer...  Still dwarf power is pretty expendable    I got about 100 idlers and they don't die as often as they my last forts.

Quote from: Number7 on May 03, 2011, 03:29:10 am

so, then you'll get your 108x108 embarks with no lag

No, the game won't allow more than 16x16.
Oh, and quantum computers would need to be perfected first. And released to common-Joe bozos like us who play DF and don't have military contacts.

You don't need a supercomputer to run a 16X16 embark . What you need is some code optimization and the sky is the limit (provided you got the memory). And I can prove it with a suboptimal algorithm .

I checked how long ( JS is slow had to use profiler or it crashed) the A* run on my 128X128 simulator... about 13 seconds . My algorithm used A* for 8 ms  and another 6 ms for itself. .  That's about  1000 times faster .The path cacher (advanced) does it in about 6ms total (2000 times faster).

The generation of the rooms from scratch takes about 90ms (automatically define rooms and access points), and 265~ ms for path cache generation between rooms . Redraw does take about half a second. The load time is about 1.5 seconds. Whatever you do don't add waypoints those use A* between them (13-14 second of runtime).

You'll notice the penalties are not even that big if you regenerate the connection graph from scratch periodically (every 500 frames). The dwarves can then reevaluate their paths from scratch  (1 room path and 1 local path)and it would take them next to no time to do. My model is also scalable . The rooms can be grouped into sub-regions, sub-regions into regions, regions into continents  , continents into planets  .

EDIT: You can't reproduce the results anymore due to an A*  optimization I did ( O(1) lookup if a node exists in one of lists) which made it run about 1000 times faster .