Print

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

[RoaryStar]

I've been reading a few threads and bug reports lately, and I've seen how many people complained about the FPS in the new version.
Lots of people have also said that the most likely culprit is pathfinding.

So, I studied a bit about it, and read this, and as a CS student, I've come up with an idea.


First, though, about the way the paths are calculated:
It uses the A* algorithm and the Manhattan heuristic.
It also uses a connectivity chart so that pathfinding doesn't use too many resources on dead ends.


The problems presented there?
Manhattan isn't the best heuristic: X+Y+Z isn't very efficient when units can move in diagonal directions.
   (this can be easily changed to Z + max(X, Y) * 1.4 + min(X, Y))
Connectivity charts take lots of resources to update, and when there's lots of changes (bridge raising/lowering, door locking/unlocking, water) it has to update more often. It also doesn't really speed up pathfinding: it only cancels paths which are absolutely not possible.


My proposed solution:
A* is an algorithm where one assigns a value to every node that is added to the list of possible nodes a unit will travel.
At the current time, if a dwarf wants to path the other side of the map, he/she has to path the entire map.

Spoiler: Example (Current Pathfinding) (click to show/hide)

##########################
#       #    #   #       #
#       =    #   ======= #
#    ===#=   #  =#      D#
####=#####=####=##########
#    ===#  ======#=======#
#    ===#        #=======#
#    ===#        #=======#
#####=##############=#####
#    ===# =======# ======#
#     =============     =#
#      S#        #       #
##########################

S is Start,
D is Destination,
# is a wall, and
= is a path the dwarf would look for.

In DF, every tile is a potential node.
What if, instead, we had another structure, a macro node? One that is placed in places like doorways or intersections, or on a large plain, in intervals of 8/10/16 tiles?
Of course, finding a way to place these will be a pain, but what if we left it to the user to define? If anything, we can define nodes for the outside, and so that would be a much faster whenever one has to path outside.
Nodes will have a connectivity chart with its closest distance to another node, pre-calculated. While calculating, you could toggle a flag so that pathfinding goes back to standard A* without the nodes.
Macro nodes will only need an X, Y, and Z co-ordinate, and any node room they're connected to.

Another structure, a 'node room', sort of, will contain a list of nodes. Simply put, it will make a boundary using its list so that it is easier to calculate starting/ending nodes.

However, when it's finished calculating the connectivity chart, the speed will be much faster.

Spoiler: Example (Node Chart/Placement/Rooms) (click to show/hide)

The letters on the left are the node it's pathing from.
The letters on the top are the node it's pathing to.
A numeral is the length of the shortest path, rounded.
A letter is an intermediate length: this is just so I have less work. In the real table, it could use that, or it could calculate all paths.
The diagonal is grayed out: the computer shouldn't look at these paths.

  A B C D E F G H I
A 0 d 4 3 d c c c c
B e 0 e e 3 e e e e
C 4 a 0 a a 4 f f f
D 3 e a 0 6 a a a a
E d 3 d 6 0 d d d d
F c c 4 c c 0 h 5 h
G i i i i i i 0 i 4
H f f f f f 5 i 0 9
I h h h h h h 4 9 0

##########################
#       #    #b-e#       #
#  a-c  a a-d#   b   b-  #
#       #    #   #      D#
####c#####d####e##########
#       #        #       #
#  c-f  #   d-e  #  g-   #
#       #        #       #
#####f##############g#####
#       #        #       #
# f-h   h   h-i  i  g-i  #
#      S#        #       #
##########################

This way, the computer does these steps:
- Dijkstra's algorithm for the start path; it uses the node room list to find which one it's in.

Spoiler: Example (Finding node room) (click to show/hide)

Dwarf is in room f-h, but the computer does not know that.
The computer has its list of node rooms.
Dijkstra starts from Dwarf.
In a few steps, it finds node H.
The list is narrowed down to f-h and h-i.
The a few more steps, it finds node F.
The list is narrowed down to f-h.
Because it's the only one left, it returns f-h as its node room.

- Dijkstra's algorithm for the end path,
- The start path chooses a random node from its room,
- Calculate the macro-nodes, which is pretty fast (use Manhattan heuristic with the X, Y, and Z of the nodes),
- Use the room node closest to the end of the path as its start,
- Path to the first node,
- On each step onto the node, or in its vicinity, path to the next node.
- On the last node, path to the destination.

This way, pathing should require less resources and time, as the path will be much more direct.

Spoiler: Example (Final) (click to show/hide)

S -> f -> c -> a -> d -> e -> b -> D


##########################
#       #    #   #       #
#     ==a    #   b====== #
#    =  #=   #  =#      D#
####c#####d####e##########
#   =   #  ====  #       #
#   =   #        #       #
#    =  #        #       #
#####f############## #####
#    =  #        #       #
#     =                  #
#      S#        #       #
##########################

Calculations:
9 heuristics calcs for Macro
~10 for S -> f
~10 for f -> c
~7 for c -> a
~3 for a -> d
~10 for d -> e
~3 for e -> b
~15 for b -> D
Total: ~ 67

Highest amount of memory used at a time:
15 nodes' worth

The old way:
~130-150 heuristic calculations and 150 nodes' worth of memory.

In the examples listed above, the old way would take ~130 to ~150 calculations, and the new way would take  ~70, and the highest amount of memory needed at once is 150 nodes' worth compared to 15. This might not be much of a difference, but it's a very small proof-of-concept example that would be expanded upon exponentially when on an actual DF map, so it would probably increase FPS rate dramatically.

tl;dr: nodes and stuff

Thoughts?

[smjjames]

That would be, quite a bit of a rewrite, and we don't REALLY know if pathing is actually causing more of the lag.

I don't know anything about coding, or pathing for that matter, so I can't comment on that.

[RoaryStar]

AI could be part of it, but pathing is still pretty bad, especially with the new trees.

About the rewrite, as I see it, he probably just needs to add the node structure and node pathing. Dijkstra's just uses a constant H of 0, which shouldn't be too bad an addition.

[GavJ]

This has some gameplay issues. Like, do the nodes also control pathing of enemies? If so, you could really majorly cheat by forcing them to take ridiculous paths to approach your fort, to give yourself time or guarantee they pass into narrowly trapped areas. If not, then it wouldn't really address a bunch of the lag... (and would require maintaining two pathing algorithms)

[Vattic]

Worth noting that you can already force the AI to take ridiculous paths and similar.

[Putnam]

This has some gameplay issues. Like, do the nodes also control pathing of enemies? If so, you could really majorly cheat by forcing them to take ridiculous paths to approach your fort, to give yourself time or guarantee they pass into narrowly trapped areas. If not, then it wouldn't really address a bunch of the lag... (and would require maintaining two pathing algorithms)

The current path costs don't control pathing of anybody but your citizens already. Not only that, but the ridiculous pathing issue is already easy enough in the current version by just having a bridge or whatever.

[RoaryStar]

This has some gameplay issues. Like, do the nodes also control pathing of enemies? If so, you could really majorly cheat by forcing them to take ridiculous paths to approach your fort, to give yourself time or guarantee they pass into narrowly trapped areas. If not, then it wouldn't really address a bunch of the lag... (and would require maintaining two pathing algorithms)

The basic idea is really just an addition: we'll use the traditional pathfinding to do it between nodes.
Enemies/caravans/animals could default to traditional pathfinding, or the computer can have a separate list of nodes (if we can get a good algorithm for placing them).

[Sergarr]

Why not go full inception and have macro-macro-nodes, then macro-macro-macro-nodes, until at some point you have all map in one (or more depending on the connectivity) node?

It would have a negative benefit of making units more likely to go through certain spaces, but it would potentially speed up pathfinding calculations immensely.

[Putnam]

And have fun recalculating the entire map every time a tile is dug out.

[Vattic]

Why not go full inception and have macro-macro-nodes, then macro-macro-macro-nodes, until at some point you have all map in one (or more depending on the connectivity) node?

I'd imagine world tiles are used for pathing over the world map.

[RoaryStar]

Why not go full inception and have macro-macro-nodes, then macro-macro-macro-nodes, until at some point you have all map in one (or more depending on the connectivity) node?

It would have a negative benefit of making units more likely to go through certain spaces, but it would potentially speed up pathfinding calculations immensely.

That would use quite a bit of RAM,

And have fun recalculating the entire map every time a tile is dug out.

If we just have a single layer, you'd only need to update an avg of three node travel lengths each time.

Also, nodes could take into account swimming and climbing costs.

[Reelya]

And have fun recalculating the entire map every time a tile is dug out.

No it doesn't require that, you use an oct-tree or similar, you only have to generate the nodes of the cleared out part. Traversing the octtree is only done when you need to compute a path.

A nice solution might be to maintain a "path network" which reaches every accessible tile (not all tiles are on the path network, the algorithm might be set to have nodes roughly every 16x16 tiles horizontally, but one on every opened z-level, nodes would be allowed to move to adjacent tiles every so often, but constrained such that they minimize the path length through them - perhaps weighted by the most common routes).

Then, to get from a->b you path just from the start to the nearest node, and from the end to the nearest node, and use the network of pre-calced stuff for the rest (basically a sped up process where you jump from node->node and use precalculated costs. This part can still be handled with A*, but you use it to traverse a weighted graph, not a grid). Opening or closing a door just means you connect or disconnect nodes. When you dig out tiles, it will see if there's any improvement in the network possible (a* through  the cleared tile, try and find shorter paths between nearby nodes), or if a new node can be spawned.

[RoaryStar]

A nice solution might be to maintain a "path network" which reaches every accessible tile (not all tiles are on the path network, the algorithm might be set to have nodes roughly every 16x16 tiles horizontally, but one on every opened z-level, nodes would be allowed to move to adjacent tiles every so often, but constrained such that they minimize the path length through them - perhaps weighted by the most common routes).

Then, to get from a->b you path just from the start to the nearest node, and from the end to the nearest node, and use the network of pre-calced stuff for the rest (basically a sped up process where you jump from node->node and use precalculated costs. This part can still be handled with A*, but you use it to traverse a weighted graph, not a grid). Opening or closing a door just means you connect or disconnect nodes. When you dig out tiles, it will see if there's any improvement in the network possible (a* through  the cleared tile, try and find shorter paths between nearby nodes), or if a new node can be spawned.

Thank you, I've never been good at explaining things clearly.

[...]
No it doesn't require that, you use an oct-tree or similar, you only have to generate the nodes of the cleared out part. Traversing the octtree is only done when you need to compute a path.

Quad-tree per level would be better, as oct-tree would be pretty much subdivided to 1x1x1 due to the nature of floors, walls, and open space.