Bay 12 Games Forum

Blue!

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.

+1 for dumplin
+1 for TLCM when it comes on
+1 Vanod

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.


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.



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.
- 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.


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?

Quote from: palu on July 16, 2014, 06:59:55 pm

Quote from: Sylveadiff on July 16, 2014, 04:42:23 pm

Quote from: nomoetoe on July 16, 2014, 03:05:16 pm

Quote from: Redzephyr01 on July 16, 2014, 12:57:52 pm

So I tamed a demon. You'll never believe what he said to me.

Spoiler (click to show/hide)

I kid you not, he said "it was inevitable."

I think he took it pretty well.

It was inevitable.

It is terrific.

It is for the best

MAAAGGGMMAAAAAAAA

Not three hours ago InsanityIncarnate died of the heat.

You are not supposed to save-scum, so why should Toady make it easier for you?

Neither is game supposed to unexpectedly crash on you, thus making you lose an hour's worth of work and thereby forcing you to savescum if you want to continue to play the same fortress.

(If I ever find out how to make a ceiling)

Ramp up the outside side of a wall, then floors everywhere.