Difference between revisions of "Path"

Latest revision as of 21:33, 29 March 2024

xTATTEREDx · +FINE+ · *SUPERIOR* · ≡EXCEPTIONAL≡ · ☼MASTERWORK☼

v50.13 · v0.47.05

This article is about the current version of DF.
Note that some content may still need to be updated.

Pathing is a videogame concept that refers to the path the AI selected to route from point A to B. It has important implications for fortress design, security design and framerate management.

Basic movement[edit]

Creatures can move in the four cardinal directions (north, south, east, and west), and four diagonal directions (northeast, southeast, southwest, northwest), as long as the target space is not blocked. This means creatures can path through diagonal gaps on the same Z-level. For example, this rat (r) can reach the cheese (%):

r	░
░	%

Creatures can move directly up or down, as long as the target space is not blocked and the movement is possible (via flying, climbing, swimming, stairs, etc.). Creatures can move diagonally across Z-levels only when both lateral and vertical movement are simultaneously possible (e.g., when using a ramp), with one exception[1] (see below). For example, this giant sparrow (S) can not attack the cat (c):

S

░

T

h

i

s

d

i

a

g

r

a

m

h

a

s

m

u

l

t

i

p

l

e

z

-

l

e

v

e

l

s

!

P

r

e

s

<

t

o

g

o

u

p

o

n

e

z

-

l

e

v

e

l

.

░

c

░

T

h

i

s

d

i

a

g

r

a

m

h

a

s

m

u

l

t

i

p

l

e

z

-

l

e

v

e

l

s

!

P

r

e

s

>

t

o

g

o

d

o

w

n

o

n

e

z

-

l

e

v

e

l

.

░

T

h

i

s

d

i

a

g

r

a

m

h

a

s

m

u

l

t

i

p

l

e

z

-

l

e

v

e

l

s

!

P

r

e

s

>

t

o

g

o

d

o

w

n

o

n

e

z

-

l

e

v

e

l

.

Exception for diagonal movement between Z levels[edit]

Diagonal movement between Z-levels is possible when the floor is missing from the space above the wall, which would otherwise block movement. Flying and swimming creatures can pass through the gap caused by the missing floor. Common causes for a missing floor include building an up-down or down stair (without the matching up staircase below it), or constructing a wall underneath tree branches.[2] For example, this giant sparrow can attack the cat, because the down stairs (>) on level 2 has removed the floor, creating a hidden gap:

S

░

T

h

i

s

d

i

a

g

r

a

m

h

a

s

m

u

l

t

i

p

l

e

z

-

l

e

v

e

l

s

!

P

r

e

s

<

t

o

g

o

u

p

o

n

e

z

-

l

e

v

e

l

.

░

>

c

░

T

h

i

s

d

i

a

g

r

a

m

h

a

s

m

u

l

t

i

p

l

e

z

-

l

e

v

e

l

s

!

P

r

e

s

>

t

o

@@ Line 79: / Line 79: @@
 == Path finding method ==
-''Dwarf Fortress'' uses a modified [http://en.wikipedia.org/wiki/A*_search_algorithm A* search algorithm] ([http://qiao.github.io/PathFinding.js/visual/ a nice demo]) ([http://www.gamasutra.com/view/feature/131954/interview_the_making_of_dwarf_.php?page=8 confirmation]), which quickly calculates a decent path between points. The A* method takes point A and tries to quickly calculate a decent path to reach point B. This path is not always the quickest path - in fact, in a game with as complicated and ever-changing an environment as ''Dwarf Fortress'', pathing probably rarely chooses the quickest path. The purpose and utility of the algorithm is to find a useful path without using a lot of processing space, balancing speed and computability.
+''Dwarf Fortress'' uses a modified [[wikipedia:A* search algorithm|A* search algorithm]] ([http://qiao.github.io/PathFinding.js/visual/ a nice demo]) ([http://www.gamasutra.com/view/feature/131954/interview_the_making_of_dwarf_.php?page=8 confirmation]), which quickly calculates a decent path between points. The A* method takes point A and tries to quickly calculate a decent path to reach point B. This path is not always the quickest path - in fact, in a game with as complicated and ever-changing an environment as ''Dwarf Fortress'', pathing probably rarely chooses the quickest path. The purpose and utility of the algorithm is to find a useful path without using a lot of processing space, balancing speed and computability.
-Choosing the nearest raw materials uses the shortcut of checking the [http://en.wikipedia.org/wiki/Manhattan_distance distance] from the [[dwarf]]'s current position, rather than an actual search. Thus, when constructing things, the valid materials list will be ordered from nearest to farthest; this, however, ignores any walls or obstacles in the way. An important part of fortress design is to be as open as possible, as more doorways will result in quicker paths (and thus better performance) as well as avoiding the hurdles of cross-map walks to find something the metric says is a short distance away. Workshops automatically path to the nearest valid raw materials; building things allows you to choose what to grab.
+Choosing the nearest raw materials uses the shortcut of checking the [[wikipedia:Manhattan distance|Manhattan distance]] from the [[dwarf]]'s current position, rather than an actual search. Thus, when constructing things, the valid materials list will be ordered from nearest to farthest; this, however, ignores any walls or obstacles in the way. An important part of fortress design is to be as open as possible, as more doorways will result in quicker paths (and thus better performance) as well as avoiding the hurdles of cross-map walks to find something the metric says is a short distance away. Workshops automatically path to the nearest valid raw materials; building things allows you to choose what to grab.
 == Applications ==