Bay 12 Games Forum

Please login or register.

Login with username, password and session length
Advanced search  
Pages: 1 ... 21 22 [23] 24 25 26

Author Topic: Improving Pathfinding. (Computer sciency)  (Read 59968 times)

Niseg

  • Bay Watcher
    • View Profile
Re: Improving Pathfinding. (Computer sciency)
« Reply #330 on: April 24, 2011, 04:45:59 am »


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.
Spoiler (click to show/hide)

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:
Spoiler (click to show/hide)
« Last Edit: April 24, 2011, 08:49:58 am by Niseg »
Logged
Projects:Path finding simulator(thread) -A*,weighted A*(traffic zones), user set waypoints (path caching), automatic waypoint room navigation,no-cache room navigation.

NW_Kohaku

  • Bay Watcher
  • [ETHIC:SCIENCE_FOR_FUN: REQUIRED]
    • View Profile
Re: Improving Pathfinding. (Computer sciency)
« Reply #331 on: April 24, 2011, 09:45:45 am »

No, as I explained, it is you that does not understand that the game has a concept called 'floors', which is not present on the horizontal version as walls need a whole tile. Those 'floors' are everywhere under and over your workshops and rooms, and they are a serious impairment to pathfinding.
If floors did not exist, if dwarves could fly and if buildings could float, then your argument would be valid, but it is not so.
Floors/Z-levels are the primary pathfinding obstacle in the game. By far.

No, as I explained, this needs to be capable of handling flying and swimming creatures, and there is no real benefit to having a pathfinding structure that penalizes vertical travel and makes the game incapable of pathfinding for two modes of travel for a minor optimization under a certain set of circumstances that you are just assuming will be more common.

The gains you are making are trivial, and the costs are serious.  It's just not worth it.
Must the game only use a single pathfinding algorithm for all creatures?
(That's a rhetorical question.)

This is the whole point around my argument. The current pathfinding algorithm has been broken to solve problems that it can't really solve. As you put it, serious costs for trivial gains.
The goal of fixing A* is not to fix the pathfinding problem (which it can't), the goal of fixing A* is to have a A* that does it's job, and then let other solutions take care of what A* can't handle.

A solution example that would improve things without breaking A* wouble be to have a different A* heuristics for creatures with different mode of travel.
This is not even some mind-blowing idea, that's just how heuristics are supposed to work.
It's also the reason why I proposed configurable A* settings options, because different fort design have different pathfinding expectancies. While those options will have minor benefits, they are also cheap to implement and have no actual costs as they are options.

That's basically saying your solution to the problem is not to solve the problem.

The reason (or at least one of the reasons) why we can't have multi-tile creatures and vehicles right now is because the pathfinding code doesn't support them.  We need serious swimmer and flier pathfinding, because there's a reason why HFS will kill your framerate right now - the clowns are all fliers that use Breadth First Search.

Your tweak doesn't actually solve any problems, and creates larger ones.  The way to solve these problems is to use a nodal structure that saves the breadth of passage and required travel mode through the nodes.

When creating a hierarchical data structure that supports storing its permitted travel types (including passage width for multi-tiles), then the hierarchical structure itself can easily handle all forms of travel, and standard A*, if it is necessary at all, assuming we don't use the "convex cube" route, is only used in intra-node travel.  This allows every form of movement to easily use the same pathfinding system, doesn't require wheel-reinvention, and actually goes through the necessary step of allowing serious non-land-based travel.

I did a few tunnels with levers, I calculated the heuristic values that way.
One of my first test that left me puzzled was an obstacle course with tunnels.
Spoiler (click to show/hide)
Strangely enough, the dwarves usually prefer to move through the underground tunnels. The tunnels have exact same traffic settings as overground tiles.
Somehow the dwarves prefer the path that's moving away both horizontally and vertically from the destination.
That only made some kind of sense after I figured the path cost debt caused by the D = 1 heuristic vs. 2 cost normal traffic. Even then that behavior is, even if explainable, still somewhat abnormal as the overland cost should be traced first. It's possible the engine is actually pathfinding several times over the same time (if the second pass has equal or better heuristic estimate), or at least overwriting early tracebacks with later ones of equal travel cost.

Presuming that those ramps are just one z-level down, you actually ARE still returning an optimal path, because the costs of moving diagonally are the same as the costs of moving horizontally. 

That far left miner would take 22 steps to reach either lever whether he went through those little tunnels or not.

What you are seeing is just a preference to move diagonally, even diagonally vertically, that is amusingly distracting, but that test doesn't demonstrate actually performing sub-optimal behavior, although it does demonstrate exploitable and somewhat illogical-looking behavior.

Those missed paths could be optimal, movement cost wise, if it managed to connect with a direct path of High traffic (1 cost) tiles to the destination. Very uncommon, and suboptimal step wise.
I'd also have to say that what you are really harping over - the traffic costs - is something that actually has a very simple fix.  Either do what the system was meant for you to do, and set all your hallways to be high-traffic zones, which nobody really does, and hence proves this a broken system, or go into the init options, and set standard traffic weighting to be 1. 

Do that, and standard traffic weight is now 1, and the heuristic assumes it to be 1, which means there's no problem.  You can just use the restricted traffic settings when you really don't want dwarves pathing through a place, like in a bedroom, and maybe crank those traffic weights up while you're at it. 

Yes, that's a problem, and it's frankly some real low-hanging fruit, but it's not a problem that anyone is arguing with, and it's not going to solve the real issues.
Logged
Personally, I like [DF] because after climbing the damned learning cliff, I'm too elitist to consider not liking it.
"And no Frankenstein-esque body part stitching?"
"Not yet"

Improved Farming
Class Warfare

devek

  • Bay Watcher
  • [KILL_EVERYTHING]
    • View Profile
Re: Improving Pathfinding. (Computer sciency)
« Reply #332 on: April 24, 2011, 10:46:58 am »

These pointless threads come up all the time, kind of ignoring the fact that Toady knows math hehe.

I'm almost tempted to write a hack that lets you guys plug your own pathfinders into DF just so you can see how pointless your ideas are... it wouldn't be that hard...
Logged
"Why do people rebuild things that they know are going to be destroyed? Why do people cling to life when they know they can't live forever?"

NW_Kohaku

  • Bay Watcher
  • [ETHIC:SCIENCE_FOR_FUN: REQUIRED]
    • View Profile
Re: Improving Pathfinding. (Computer sciency)
« Reply #333 on: April 24, 2011, 10:47:37 am »

Something else when we are talking about splitting up pathfinding between movement types...

There is a cost you potentially aren't thinking about if you are actually using different connectivity maps.  We currently have fully aquatic, amphibious, walker, flier, amphibious flier, magma-walker, magma-swimmer, and all-terrain types of movement.

Now multiply all those types of movement by the number of different vehicle sizes we will be allowing in the game.

That's how many connectivity maps you will need if we don't use a system designed to allow all the different types of movement we will be needing to track in this game over the long haul.

On top of this, every time you change the map in any way (such as by even having water flow), you need to go through a connectivity map update check on all of those connectivity maps, as well. 

The requirements for this system is not that it returns an optimal path, but that it does not unduly strain the memory requirements of the system, that it is lighter on the processor (which really means making less memory fetches), that it is capable of handling constantly changing maps while spending the least time having to update the pathfinding data structures, and finally, that it returns an at least reasonably optimal path.

Oh, right, and then we have to go into the matter of having siegers that are capable of digging through walls and bridging over trenches and building ladders to climb walls. 

This system cannot be designed from the point of view that only dwarf movement matters. 

Building a system where all units, regardless of movement type uses the same map, but relies upon the different nodes having specific movement types and width allowances recorded is the only sensible option, and if we are doing this, there is little need to have different pathfinding algorithms for every movement type, since the simple node connectivity and movement types allowed recorded in the nodes themselves will handle all those other problems for you. 
Logged
Personally, I like [DF] because after climbing the damned learning cliff, I'm too elitist to consider not liking it.
"And no Frankenstein-esque body part stitching?"
"Not yet"

Improved Farming
Class Warfare

Phoebus

  • Bay Watcher
    • View Profile
Re: Improving Pathfinding. (Computer sciency)
« Reply #334 on: April 24, 2011, 11:04:20 pm »

the other method is a modified A* (don't kill me) i have a Wikipedia understanding of A* (meaning i looked at the Wikipedia animation) using the animation as an example, the program traces a line towards it's target. the line hits the wall, and instead of expanding from there, it follows the wall in both directions until one becomes free to move again. the program then begins to trace between these points, and if it collides again it repeats this task. then, after it arrives, it begins to continue it's course. i might create an example when im not exhausted and can think.
That algorithm isn't applicable to DF because the heuristic is optimized for 2D. In DF there can be stairways/ramps in the middle of the room and that modified A* would just walk around them/ignore them.
Logged

Uristocrat

  • Bay Watcher
  • Dwarven Railgunner
    • View Profile
    • DF Wiki User Page
Re: Improving Pathfinding. (Computer sciency)
« Reply #335 on: April 26, 2011, 03:42:10 am »

These pointless threads come up all the time, kind of ignoring the fact that Toady knows math hehe.

I'm almost tempted to write a hack that lets you guys plug your own pathfinders into DF just so you can see how pointless your ideas are... it wouldn't be that hard...

Now *that* would be an interesting mod.
Logged
You could have berries on the rocks and the dwarves would say it was "berry gneiss."
You should die horribly for this. And I mean that in the nicest possible way.

Niseg

  • Bay Watcher
    • View Profile
Re: Improving Pathfinding. (Computer sciency)
« Reply #336 on: April 26, 2011, 06:52:23 am »

These pointless threads come up all the time, kind of ignoring the fact that Toady knows math hehe.

I'm almost tempted to write a hack that lets you guys plug your own pathfinders into DF just so you can see how pointless your ideas are... it wouldn't be that hard...

Now *that* would be an interesting mod.
:-\ I don't think I'll take any part of *that* . I'm here to suggest stuff not to "fix" the code through hacks. Controlling the game with external apps is one thing, changing the game  engine is borderline copyright infringement ~ .

I'm not  sure why devek is so resistant to any path-finding related suggestions. He might be right that path finding improvements would be a waste of time because it might not take as many CPU resources as we think. My limited test didn't suggest memory thrashing .

It still seems logical that path finding improvements would lead to FPS improvement because that what all creatures do most of the time. Recently I built the bridged snake access:
Spoiler (click to show/hide)

It seems that after enabaling bridges dwarves still go along the snake. Some of them did repath - it might be related to bumping into each other.

I think that repathing frequency along with the big penalty on blocked paths can cause slow down .I'm not really sure. some people suggest atom smashing helps. Maybe the search through many items isn't optimal. If anyone searching through items check its accessibility using A* it might cause  a huge slowdown when there are many items inaccessible.

This is where the "Room splitting suggestion" can help - help a lot. I'm now in the process of creating one in my simulator . my current scheme of "waypoint rooms" is not always going to find the path because of it's naive  way of selecting rooms (it assumes it's either in the room closest to it or a disconnected  neighbor that of  that room ). This point to a room selection problem and instead of fixing something that sometimes work I advanced to a well defined room scheme which is the natural advancement.

even though waypoint room sometimes don't work when it does it gives great results of about 15 node visits compared to 800 of A*. The blocked path penalty is about 15 node visit compared to the number of accessible nodes of the map (that's about a maximum 1000 in my simulator). Still it only work for special cases and like this . When it's blocked in the corner it does about 700 node visits because I  let it run wild ( high limit on search distance) in attempts to reach the destination .

My new room definition algorithm would make the room selection very deterministic which would save pathing retries and other problems related to the waypoint scheme. After that I'll add a room update scheme and when everything is done I'll switch to 3d . After that I may convert the mechanics into c code or find other ways to grind it for performance testing (JS's has pretty bad performance).
Logged
Projects:Path finding simulator(thread) -A*,weighted A*(traffic zones), user set waypoints (path caching), automatic waypoint room navigation,no-cache room navigation.

devek

  • Bay Watcher
  • [KILL_EVERYTHING]
    • View Profile
Re: Improving Pathfinding. (Computer sciency)
« Reply #337 on: April 26, 2011, 08:52:00 am »

:-\ I don't think I'll take any part of *that* . I'm here to suggest stuff not to "fix" the code through hacks. Controlling the game with external apps is one thing, changing the game  engine is borderline copyright infringement ~ .

Hacking isn't copyright infringement. Besides, Toady will never sue me because I would never do anything to harm him, I <3 the toad.

I'm not  sure why devek is so resistant to any path-finding related suggestions. He might be right that path finding improvements would be a waste of time because it might not take as many CPU resources as we think. My limited test didn't suggest memory thrashing .

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.

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.

It still seems logical that path finding improvements would lead to FPS improvement because that what all creatures do most of the time.

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.
Logged
"Why do people rebuild things that they know are going to be destroyed? Why do people cling to life when they know they can't live forever?"

tps12

  • Bay Watcher
    • View Profile
Re: Improving Pathfinding. (Computer sciency)
« Reply #338 on: April 26, 2011, 09:42:06 am »

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.

Totally agree with your general point, you don't even know what you know until you profile. And you need to interpret the results correctly: even if the pathfinding function does end up accounting for a huge chunk of processor time when the game is profiled, it may be entirely due to some easily-detected edge case, meaning efforts to improve the pathfinding algorithm as a whole are unnecessary (if not counterproductive).

If "just wait until Toady gets around to it" isn't enough for people, then a real investigation into pathfinding should start with trying to reproduce the existing DF pathfinding on actual maps (via dfhack) and establish plausible test scenarios that demonstrate the slowdowns observed in real games. You can't make any progress on a solution until you know what problem you're trying to solve.

I was going to quibble with the idea that math knowledge might imply any particular ability when it comes to algorithms, but actually in this context I think it's fair enough. At least until someone has driven their own racecar around an identical track and has some evidence to back them up, it's unlikely that even a knowledgeable outsider's uninformed speculation is going to be any help.
Logged

Niseg

  • Bay Watcher
    • View Profile
Re: Improving Pathfinding. (Computer sciency)
« Reply #339 on: April 26, 2011, 10:14:57 am »

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  ;D.
Logged
Projects:Path finding simulator(thread) -A*,weighted A*(traffic zones), user set waypoints (path caching), automatic waypoint room navigation,no-cache room navigation.

Draco18s

  • Bay Watcher
    • View Profile
Re: Improving Pathfinding. (Computer sciency)
« Reply #340 on: April 26, 2011, 10:17:49 am »

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.

Math professor at a university.  I don't recall which one.
Logged

devek

  • Bay Watcher
  • [KILL_EVERYTHING]
    • View Profile
Re: Improving Pathfinding. (Computer sciency)
« Reply #341 on: April 26, 2011, 10:50:33 am »

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?!

It is a code flow analysis produced from the binary. Very useful when doing forensics. The large wide part at the top is where it switches on every item type (weapon, box, plant, etc). It is intentionally zoomed out far enough to not give any specific information hehe.

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 .

Learning and applying this stuff is a good thing. Sadly, most colleges don't teach up to date programming techniques :/ CPUs today are fast, like REALLY fast but memory isn't very fast. When you get it, you'll understand why it is just as expensive to path up one z-level as it is to path out 16 tiles horizontally. Check out this pdf from Sony for example...

http://research.scee.net/files/presentations/gcapaustralia09/Pitfalls_of_Object_Oriented_Programming_GCAP_09.pdf

It takes a common programming case and improves its performance from 20ms to 3ms with simple reorganization. The case is very similar to a lot of processing DF does :)
« Last Edit: April 26, 2011, 10:55:03 am by devek »
Logged
"Why do people rebuild things that they know are going to be destroyed? Why do people cling to life when they know they can't live forever?"

tps12

  • Bay Watcher
    • View Profile
Re: Improving Pathfinding. (Computer sciency)
« Reply #342 on: April 26, 2011, 11:23:42 am »

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.

You can't, but you can maybe get far enough to know whether you are even asking the right questions.

You know DF uses A* with path costs modified by traffic designations, you know the heuristic used, and dfhack gives you access to actual game maps. So start by reproducing the DF pathfinding algorithm and observing its performance running on real maps.

Establish sets of test pathing requests (straight lines, expected worse case paths, impossible ones, paths between random tiles, different sets of "typical" requests as best as you can determine from surveying units in active games) to act as baselines for comparison.

At this point you can check your work: if you can make a terrain or traffic designation change in your test system that has a significant impact (positive or negative) on pathing performance, then you should be able to observe a similar result from making the same change in the actual game, and vice-versa. If one of your test cases does much worse than another, then see if you can get DF to slow down by recreating it in-game.

Only at that stage can you start to explore how alternative algorithms perform in comparison. And if your test cases were representative you'll have an idea whether any improvement you come up with might have an actual impact (i.e., improving the worst case may not mean much if the worst case is rare). When you think you have an improvement, you can grab another game off DFFD and confirm your results on fresh real data.
Logged

devek

  • Bay Watcher
  • [KILL_EVERYTHING]
    • View Profile
Re: Improving Pathfinding. (Computer sciency)
« Reply #343 on: April 26, 2011, 11:38:55 am »

DFhack doesn't parse the pathfinding information in a mapblock, and if there were any issues or bugs that is where they would reside. He could reconstruct the information itself, but that may not match up with what DF is using.

I'm actually messing with that area right now due to a different reason(investigating smarter ways to make Foreman cut down trees)...
Logged
"Why do people rebuild things that they know are going to be destroyed? Why do people cling to life when they know they can't live forever?"

tps12

  • Bay Watcher
    • View Profile
Re: Improving Pathfinding. (Computer sciency)
« Reply #344 on: April 26, 2011, 12:10:43 pm »

Yeah, I don't mean for finding bugs in the implementation or anything, just for benchmarking alternative pathfinding routines. Or does dfhack not give you traffic designations? I thought I saw it in the headers.
Logged
Pages: 1 ... 21 22 [23] 24 25 26