Print

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

[Veroule]

This is a very different solution to the current perceived pathfinding slowdown.  Please don't bother bringing up other techniques that have been discussed before.  To understand this you should have a basic idea of how A* works; if you don't have that knowledge please get it before commenting.

Throughout this post I will use XD, YD, ZD for where the dwarf is; X, Y, Z for the target object location; and XW, YW, ZW for where that object needs to go.
The basic premise is that most jobs currently use a Pythagorian calcluation on the Cartesian coordinates to determine which object to use.  This involves looping through all objects, calculating the 'distance' for each that is applicable to the job.  Then targetting the location of the one found to be 'closest' for pathfinding.  The 'distance' above results in a single precise calculation for the initial H factor in the A* alogarithm.  That number then is recalculated with each step to determine if movement was in the correct direction.
The first question is always, "Should we calculate a path?"  This seems to already be handled in a very quick fashion for all types of jobs.  Perhaps it could be made faster, but it is very difficult to guess.  I will skip past this question.
The next question is, "Where should the path go?"  In the case of a workshop job it needs to go to the object closest to the workshop.  A dumping job has mostly the same answer, we want an appropiate object closest to the dump site.  The answer to which object is closest can only be accurately calculated by pathing, an obvious conundrum.

In order to solve this catch22, sort the objects based on the Z axis as they are checked for appropiateness.  Then compute the 'distance' only for those that have a Z=ZW.  If this results in no values being computed then the pathing will have an H factor of MAXINT initially.  I will also suggest that the 'distance' calculation be simplified at this step.  The simple form used is D=abs(X-XW)+abs(Y-YW), then the lowest value calculated is used as the H.

With an initial H value decided we can begin pathing.  Each step of the path should check for 2 things.
1: We are at an appropiate object.  By indexing the start and end points in the Z sorted list of objects the testing loop can be kept small.  To make the looping even smaller it only needs to be checked when the H factor of the destination tile is 0.  The H value for each step in the path would be the previous tile's H minus 1 (2 when the step was a diagonal).  If the H goes negative or reaches 0 then the tile is checked for a match.  If an object isn't there then 'distances' are computed based on that location and the correct H is set for that tile.

2: We have reached a stair/ramp.  When this occurs it is time to compute more 'distances'.  In this case we are looking at the Z level that is being led to, and calculating an H value for the outlet of the stair/ramp based on objects in that level.  The list of objects is already sorted, and we have an index that is 1 away from anything on that level.  If the calculated H for objects on the new Z level is less than the H of our current stair tile then we put that calculated H+1 at our stair location.  This will result in the up/down step having the correct H.

Let's take a moment to consider the obvious implications of this change to the alogarithm.  The A* method uses the H factor to determine if it is searching in the correct direction.  So far the change is completely breaking that, and making the path calculation more of a flood fill method.  When we consider that most fortress layouts already cause the H value of A* to work against us this doesn't seem like a bad thing.
The result we have so far is a path from XW, YW, ZW to the object X, Y, Z.  We actually need a path from XD, YD, ZD to X, Y, Z and a path from X, Y, Z to XW, YW, ZW.  The second path is just a matter of reversing all the directions in the path we currently have.  The first path is no longer looking for an object it is looking for a specific location and might need to be calculated.

We have to return to that first question, "Should we calculate a path?"  The reason to ask this again is because the dwarf might already be at the workshop. This would mean we have a perfect path already.  If that is the case the workload has been cut by more than half.

Assuming it is not the case we are back to calculating a path.  The second question, "Where should the path go," seems to be answered; in reality it isn't answered.  We already computed a path to the object, and it is very likely that some portion of that path will be valid for this new path.  The object we are trying to path to in this case is a point in our existing path.  We can use the exact same alogarithm described above by looking at the locations that first path went through as possible destinations.  Once the new path connects with the one we already have determined, the 2 paths can be assembled into a single one.
Next we need to look at what happens when the dwarf decides to get a drink in the middle of the job.  They aren't cancelling the job.  It makes the most sense to keep the path from the object to the workshop, and keep that object tasked to the job.  This does present a problem for things that can rot.  In order to handle this the object's original location should be kept available until the object has been changed and multiple taskings  should be able to be set on each object.  When the cook drops something in the middle of bringing it to a kitchen it would be tasked to be brought back to the stockpile and tasked to be cooked in the kitchen.  The return to stockpile would be putting it back exactly where it was and would use the part of the path to the kitchen  that the object had travelled.  The cook returning to duty before the object made it back to the stockpile would cancel the return job and could then path to the point the object is dropped at, and we would already have path from that point to the kitchen.
We should also look at some other types of things dwarfs like to walk to.

Mining, detailing, and woodcutting are the first to come to mind.  Here the object we use is the designation, and the workshop location is actually the dwarf.  This eliminates the top-left scanning currently used with these jobs.  The path is always computed based on what is closest to the dwarf.

Another one to examine is getting a drink.  The objects in this case are available barrels containing drinks.  Again we find that the change in method is an improvement in dwarven intelligence.
The real question is does this method make anything faster.  To answer that we have to compare what is already being done with the changed alogarithm.
1: Accumulating a list of viable targets.  Done in both.
2: Calculating 'distances' to targets.  Done once in A* for all targets.  Done repeatedly as needed in the new method; which could be slower.  Reduction of precision in the new method and restricting calculations by Z should result in speed equality.
3: Examining tiles in the wrong direction.  This can occur with both methods because of layouts.  I can't determine any clear difference in quality on this point.
4: Walking past a viable object.  A* does this all the time because of the 'distance' calculation determining a fixed destination.  The object based method changes the destination as needed to home in on what is closest.  This should frequently result in shorter paths.

I believe that last statement is what will result in faster pathfinding while improving dwarven intelligence.

[numerobis]

I don't understand how what you're proposing isn't just Dijkstra's algorithm starting from the workshop.

[Footkerchief]

In order to solve this catch22, sort the objects based on the Z axis as they are checked for appropiateness.  Then compute the 'distance' only for those that have a Z=ZW.  If this results in no values being computed then the pathing will have an H factor of MAXINT initially.  I will also suggest that the 'distance' calculation be simplified at this step.  The simple form used is D=abs(X-XW)+abs(Y-YW), then the lowest value calculated is used as the H.

I don't follow this part.  What happens if none of the suitable objects satisfy Z=ZW?

Also, many players have fortresses that use Z-levels heavily, sometimes to the point of being taller than they are wide.  Won't this make things worse for them?

[ilsadir]

Uh.

Selected Object = Object with minimum sum of distance to dwarf + distance to workshop.  Then standard A* to object and then to workshop.

Problem solved.

[numerobis]

@ilsadir: which problem is solved by that approach?  And how do you measure distance?

[Veroule]

I don't understand how what you're proposing isn't just Dijkstra's algorithm starting from the workshop.

It does actually start very similarly to the Dijkstra because the H is not tested directionally.  When the H value gets to 0 then all the objects on that level are checked again for 'distance' and the H at that tile is set correctly.  If you draw up a diagram you should find it will spread in a fashion that is different then both A* and Dijkstra.

Let us also consider a situation where we need to path from 50,50,1 to 50,50,2.  Here the A* alogarithm has a starting H of 0 and the H is increasing as the path spreads.  If it encounters a stair in the wrong direction then after it follows that stairway the F+H will become the lowest, and that entire level will be pathed out until it has spread just as much as the previous level.  This is a situation that should be avoided.  My proposed method makes the spread continue evenly until the right Z level is reached and then makes that its focus area.

In order to solve this catch22, sort the objects based on the Z axis as they are checked for appropiateness.  Then compute the 'distance' only for those that have a Z=ZW.  If this results in no values being computed then the pathing will have an H factor of MAXINT initially.  I will also suggest that the 'distance' calculation be simplified at this step.  The simple form used is D=abs(X-XW)+abs(Y-YW), then the lowest value calculated is used as the H.

I don't follow this part.  What happens if none of the suitable objects satisfy Z=ZW?

As I stated we use MAXINT for the H value.  This makes the pathing spread according to the Dijkstra method until it finds a stair.  On finding the stair it would then attempt 'distance' calulations for the new level.  Assuming some items are found the result would be less then the current H and that would then set our search path to spread there instead of all over the previous level.

Also, many players have fortresses that use Z-levels heavily, sometimes to the point of being taller than they are wide.  Won't this make things worse for them?

Examining the current behavior you find that stones at 50,50,10 and 50,50,1000 are considered to be the same distance from 40,40,10.  In fact if the stone at 50,50,1000 happened to be created before the one at 50,50,10 then the path will be made to go to 50,50,1000.  I really don't see any way to make this worse.

[Mel_Vixen]

Do you have any numbers/spreadsheets/diagrams on the efficience of your approach? Or maybe even a little test programm?

[Veroule]

Quite right, the proof is in the pudding.  I haven't made any diagrams or a test program yet.  I just finished the conceptual design this morning.  I will put together some diagrams over the next couple of days and then post them.

If everything checks out during that process then I will spend some time modifying an A* test program to use my method.  I have one that does single stepping of the A* alogarithm that would be excellent to demonstrate the change.  I would just have to add multiple Z levels and multiple objects.

[Mel_Vixen]

Nice. It would be neat if you can hand out the source-code too if you are done. Also i hope it does get some more efficience on the long run .

[H]

The most efficient (time efficient, not memory efficient) algorithm to find the closest object of some class to a fixed point (closest dump-site to an item, closest stone to a mason, etc) probably is as follows:

First generate a comprehensive list of the items of that class ordered by their as-the-crow-flies distance to the point (use a priority queue ordered by distance when generating it).

Now we need to generate an upper bound.  Take the first item and A* path find to it; don't throw away the open and closed list.  Save that item and the distance required to walk to it as an upper bound.

Consider the next item on the list.

Is it's as-the-crow-flies distance greater or equal to the distance to the upper bound?  If so stop the search - the current upper bound item is the closest item of the desired type.

Otherwise check that item against the closed and open list generated by the previous round of A*.  If it is in that list we already have a walking-distance to it.  If that distance is less than or equal to the distance to the previous upper bound it becomes the new upper bound and we start over with the next item on the list.

Otherwise we need to path find to it.  A* using the existing closed and open list.  As before if it is closer than the previous upper bound it becomes the new upper bound.

The reason this algorithm has an advantage in efficiency is as follows: First by lowing the upper bound as we go in the average case we will only end up checking the distance to one or two item.  Since in the process we have already pathed to them this is only going to take 2 or 3 times as long as an algorithm that simply picks the closest as-the-crow-flies item, since you still have to generate a path to it afterwords.  Secondly, by saving the open and closed lists a number of problem cases become much more manageable.  For example: all the items of the desired kind may be in a stockpile at the end of a maze.  In this algorithm we only have to path through the maze once.

[Veroule]

H, that method does appear to be quite efficient.  Running it through my head as many ways as I can imagine always finds the closest object.  Time wise I think you are right it would rarely take longer than 3x the computational time of 'distance' all objects, sort for lowest, path once.

There is one sort of layout that my mind keeps saying would take much longer, and that is a workshop above and east of a stockpile with the stair some distance away to the east.

The reason this layout presents a problem is because nearly all the items would have a 'distance' less then the path distance, and most would be excluded from the initial open and closed lists.  The pathing would have to extend through all the items to decide that it did find the closest right from the start.

I am not against an increase in computational time when it makes a commensurate impact in dwarf walking time.  Getting the dwarf to always grab the closest thing could have a significant impact on walking times. The outlying cases with the technique you have described could cause the computational time to increase too much, making an overall downgrade.

While I didn't include it in my original proposal of alogrithm; I am considering whether it would be possible to have both multiple start and end points computed at the same time.  Meaning from lists of M and N points find the shortest path that runs from one entry in M to one entry in N.  This would be especially useful for all manner of jobs.  Imagine the job queue selecting which dwarf does the job based on which one will get it done the quickest, and having that computation already be the completion of the pathing required to do the job.

I know it is doable, I just have to proof it.

[Mikademus]

I'm always interested in new, pragmatic path finding solutions and this seems indeed interesting. As was asked above, could you provide source that would allow us to test and time it ourselves? I'm afraid code is more conductible for understand than long explanations for these kinds of problems.

[Veroule]

I'm always interested in new, pragmatic path finding solutions and this seems indeed interesting. As was asked above, could you provide source that would allow us to test and time it ourselves? I'm afraid code is more conductible for understand than long explanations for these kinds of problems.

Most definitely.  I am still plugging along on graphs by hand as I tune the concept.  I have rejected about 30 different variations to A* based solely on how the H was being handled.  A few of those variations might be reconsidered as I add the G to my graphs.  When I am solidly confident that have vetted all the rules and am accounting for all variables then I will put it together into code.

I will post a complete explanation of the procedure at that point as well as code.  The explanation would mostly useless to Toady, since it would mean he would have to write the whole thing again.

[Mel_Vixen]

Veroule is it possible to make the testprogram so modular that we donmt need to write a new programm for every algorithm we want to test?

[Veroule]

I worked through quite a few graphs on the concept.  For 1-1 pathing in wide open terrain the standard A* definitely looks at fewer locations.  Determining speeds of particular alogrithms from the graphs is a bit difficult.  I moved on to writing a test program for this reason.

The test program is going to have quite a few different choices in how to calculate the path:  1-1, 1-many, many-1, many-many, standard A*, and Dijkstra.  The use of stairs, returning multiple paths, 26 direction path results, and a few other things are also being designed in as options.

Since this project is an attempt to produce something that could be used to improve DF; I am designing it so that only 1 section of code needs adjustment to be thread safe.  I also have started considering how to make it do a 2 stage pathing.  The project is getting close to being a full library at this point, so it also gets my additional requirement of easily redirecting all heap releated functions.  I have another project that is going to need good pathing calculations, and requires handling for different size units.  I will be putting something for that in there as well.  Expect it to take me a while.

Yes, it will be very modular.  The test program itself is little more then a random maze generator that formats the maze data for pathing, and provides timing on each test.