Print

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

[CobaltKobold]

I don't think the pathing library should be responsible for handling AI.

At some le'el, it becomes the AI. "Do I take the path nearer the goblin archers or the one past the spiked pits?"

[Urist McDepravity]

"Do I take the path nearer the goblin archers or the one past the spiked pits?"

Thats a good point, actually. Although it should not be handled by pathing lib, but rather it should provide ALL possible paths, one for each way of traversing the graph.

[Shades]

"Do I take the path nearer the goblin archers or the one past the spiked pits?"

Thats a good point, actually. Although it should not be handled by pathing lib, but rather it should provide ALL possible paths, one for each way of traversing the graph.

No it should return the single shortest* path based on whatever criteria as passed to it. If this includes a don't go within X of goblins that is fine.

_{*probably shortest or close enough to make no difference.}

[Silverionmox]

Earlier all-edge comment:

The cliff case is meaningless: You could have a tile group for the upper path, and one for the lower. Where the edges of the groups cross, you could describe the movement costs between them. The advantage is that you don't have to store the data of every identical sky tile in an empty 10x10x10 cube, only where it connects to other groupings. When breaking up the grouping, you simply transfer the edge data, either to the tile itself(unlikely) or to the new edge.

Also, a suggestion: maybe put a slight extra weight against direction changes? Not tile-based, but a flier going up over a mountain wouldn't follow the ground exactly... (Of course, such behaviour might develop naturally...)

Arguably, the flier will automatically fly at least one level above ground as soon as rock, trees etc. are proper obstacles. Also, air currents will make some directions easier than others so they might be inclined to soar up along with warm air and then glide down towards their destination and descend.  Personal preferences also could play a role. Prey birds would habitually stay sufficiently far above ground as a matter of habit, to avoid predators.

How well does A* handle different costs depending on (corr.) direction? This will be useful for streams, air currents, differentiating uphill/downhill, etc.

[Mel_Vixen]

The Bresenham algorithm is fundamentally aesthetic in nature and doesn't help you find the shortest way between points in any meaningful way. Sure, it might look better if creatures moved in what looks like straight lines towards their goal in open areas, but it has no effect on the cost of the path, and it is more expensive in implementation than just "if x < targetx && y < targety then up-right" (since Bresenham would require storing extra values and performing computations slightly more complex than the above, each step).

I know that it was created for shading but actually it can help you to find the shortest path between two points since in nature the shortest path between 2 nonmoving points is a straight line. Our points would be the access and exit points of a TCZ - given that said TCZ is rectangular.

You might now answer that In tile based games the a straight line isnt the shortest path,thanks to the "New york" Problem, but toady iirc circumvents the "New york" Problem by having diagonally movement being less expensiv then pure vertical and horizontal movement.

Secondly the the dwarfes iirc already remember their paths so they dont have to calculate them in every turn/frame. The Bresenham can return the tiles of the path while your way ignores that posibility.

And now comparing your method with my method.

your variant: (a made it a bit more pseucode like)

Code: [Select]


x, xtarget, y ytarget     // get the coords of dorf and dorfs target
xst, yst                      // x and y steps

if x = targetx
then
   xst = x;
else
  if  x < targetx
  then
    xst = x+1;
  else
    xst = x-1;


if y = targety
 then
    yst = y;
 else
   if  y < targety
   then
     yst = y+1;
   else
     yst = y-1;
 

store (xst, yst)


the problem with your code is that it works fine in a "New york" world but its rather hard to incooporate a non "New york" world where a straight line is the better movement. It works also nice for moving targets actually. 

In the worst case you compare 4 times 2 variables and you have 2 additions per iteration.

my variant:

Code: [Select]


get xa, ya  // get start coordinate
get xe, ye //  get end coordinate

d = 2×Δy – Δx       // Δy = ye - ya ; Δx = xe - ye
ΔO = 2×Δy           
ΔNO = 2×(Δy − Δx)
y = ya
store tile (xa, ya)
for every  x of xa+1 till xe
    if d ≤ 0
    then
        d = d + ΔO
    else
        d = d + ΔNO
        y = y + 1
    store tile(x, y)

The worst case here are 10 calculations for initialisation and , per iteration,  2 times comparing variables and 2 calculations. The bresenham would also work fine with DFs non "New york" world. The contra is that it doesnt work for moving targets.

if we say that calculations and comparings are each 1 clockcicle your code is better on the first 4 steps the dwarf does while in the 5th they reach an equilibrium and in the 6th the abused Bresenham gets better.

But actually i am not very far in this stuff yet since i do normaly other stuff.

[Sunken]

1: You're working from an incorrect assumption. Diagonal movement and orthogonal movement cost the same in DF.
Edit: Scratch that, there's a sqrt(2) factor in there

2: As for costs, you're comparing a cached version of your algorithm with a non-cached version of mine. Hardly fair! Silly-move can be cached just as easily as a Bresenham path, except it would be pointless since computations are far less expensive than memory access nowadays.
Edit 2: Heh, scratch that too, I misread your claim.
Still, Bresenham will require the storage of the d parameter, and the final path will not actually cost any less than the silly-move one; it will just distribute the diagonal movements differently. Plus, it disallows TCZs (as presented by me, as opposed to rectangles or other strictly convex regions) and, as you say, isn't optimal with moving targets.

[Mel_Vixen]

A chached version of your algorithm would look like this:

Code: [Select]

x, xtarget, y ytarget     // get the coords of dorf and dorfs target
xst, yst                      // x and y steps

As long x!=xtarget && y!=ytarget
do
if x = targetx
then
   xst = x;
else
  if  x < targetx
  then
    xst = x+1;
  else
    xst = x-1;


if y = targety
 then
    yst = y;
 else
   if  y < targety
   then
     yst = y+1;
   else
     yst = y-1;
 

store (xst, yst)

Which would haven even more (2) compartions.

But as i said i am not that good at this stuff. normaly i do Assembler where i can count my clockcicles.

[Sunken]

Made an edit, but too late. Pasting my rebuttal here:

Still, Bresenham will require the storage of the d parameter, and the final path will not actually cost any less than the silly-move one; it will just distribute the diagonal movements differently. Plus, it disallows TCZs (as presented by me, as opposed to rectangles or other strictly convex regions) and, as you say, isn't optimal with moving targets.

[Sunken]

Not that moving targets are really at issue here. Short-distance pathfinding is not what's costing us FPS.

[Mel_Vixen]

The Path costs may be the same but the pathcosts are in a homogenous rectangular Tcz anyway ignorable if both algos get the same path. What is important is the CPU time which is used. Also i dont see a to big problem in mixing symetrical Pathzones with asymetrical Tczs. Depending on in which type of pathzone our dwarf is a different pathalgorithm (silymove, floyd-warshall, dijkstra, Bellman-ford, abused bresenham) might be the best and less timeintensiv.

[Sunken]

Planning movement within a rectangle is not a problem, no matter which algorithm you select. Nor is it within TCZs, using silly-move. The computational costs for these are all absolutely negligible, I think.

The problem is the search. What is needed is a reduction in branching factor and search tree depth (and a good heuristic). And it's my belief that TCZs will have a better impact on these key factors than rectangles will.

But it's true that in principle it would be possible to mix zones of different types. It would require more programming work, and a disciplined, modular structure, but it's not infeasible.

[Mel_Vixen]

Actually the faster we calculate one path the faster we can go to the next dwarf.

Right now toady uses a algo that supports 200 on 2GHZ. (he uses a normal A* without heuristics etc. iirc) if we find ways to make the pathfinding  10% faster we can support with 2GHZ 220 dwarfs. The tradeofs just need to be acceptable as in that they schouldnt be to memory expensiv and schould give atleast semiperfect paths.

Heuristics, trees and branches are one point in the equeation. but what and how things happen inside zones, tcz, and what not is i think important too.

[shadow_slicer]

But I've already mentioned that simply using the Bresenham algorithm wouldn't help things at all. That is not a pathing algorithm. It is a method for converting a path (a line) to a list of points on a grid which look aesthetically similar to that path. It doesn't consider the cost of traversing each possible edge, or going around obstacles.

In analyzing the algorithm you are starting from the basic assumption that you want to go from point A to point B in some convex shape which contains no obstacles. You don't describe how the points A and B get determined (which is important), how the convex shape is defined and fits together with the rest of the map, or how it is known that the shape contains no obstacles. Additionally, you are assuming that the only shortest path is a "straight" line. In fact there are a large number of similar paths which are not straight lines (which consist of some combination of diagonal and non-diagonal movements) which all share the same cost.

As Sunken so aptly put it:

Planning movement within a rectangle is not a problem, no matter which algorithm you select. Nor is it within TCZs, using silly-move. The computational costs for these are all absolutely negligible...
The problem is the search. What is needed is a reduction in branching factor and search tree depth (and a good heuristic).

The thing is the that good zone design and branching is probably going to provide 95% of the improvement we'll see. Whatever happens in zones (if they are suitably designed), is not going to help even 1% (probably less than 0.1%). Additionally, as Sunken has mentioned, silly-move is much simpler than Bresenham's algorithm (and has fewer problems in zones that are not obstacle-free).

As far as the zones and branching goes, however, I'm not so much of a fan of the TCZ's that Sunken is proposing. I don't see the advantages of silly-move over A* for the scenarios silly-move is applicable for outweighing the flexibility of A*. Additionally I think we can do better if we allow for zones that do not satisfy TCZ (such as a windy passage that doubles back), but which are trivially pathable with A*. I also think that zones should be 3D since this allows for similar windy passages in the z-direction (and the sky could be one gigantic zone).

[Richards]

Has anyone corresponded with Tarn about supporting a team to create an official path finder utility for DF?

[CobaltKobold]

Has anyone corresponded with Tarn about supporting a team to create an official path finder utility for DF?

I'd wait until something actually appeared.