Pathfinding accuracy rewrite

Discussion of Maia's on going development, including modding.
Ortwin
Posts: 84
Joined: Tue Sep 04, 2012 12:21 pm
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: Pathfinding accuracy rewrite

Post by Ortwin » Sat Apr 20, 2013 7:36 pm

About map size... how deep will we be able to go?
If we are getting a cube with a 2km rib size, I sure hope there will be caves and cave-critters as well...

In DF, the most 'fun' was deep down below. The surface doesn't really pose a challenge as soon as you build a draw bridge (and perhaps a lava shower to flush the vermin of ma lawn).

User avatar
Tikigod
Posts: 152
Joined: Thu Apr 04, 2013 9:29 pm
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: Pathfinding accuracy rewrite

Post by Tikigod » Sat Apr 20, 2013 10:59 pm

Ortwin wrote:About map size... how deep will we be able to go?
If we are getting a cube with a 2km rib size, I sure hope there will be caves and cave-critters as well...

In DF, the most 'fun' was deep down below. The surface doesn't really pose a challenge as soon as you build a draw bridge (and perhaps a lava shower to flush the vermin of ma lawn).
I don't think any kind of vertical expansion has been mentioned has it? Just surface expansion, with the surface split between open terrain and caverns.
Violence is the last refuge of the incompetent - Isaac Asimov

My channel. Game recordings & old 3D art assets I've made.

User avatar
SimoRoth
Site Admin
Posts: 1106
Joined: Sat Jul 14, 2012 11:28 am
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: Pathfinding accuracy rewrite

Post by SimoRoth » Sat Apr 20, 2013 11:47 pm

There will be a lot of layers eventually. Not hundreds, but at least 5-10 by mid summer, this isn't a cube based world, but you will connect layers with ladder and lift shafts. :)

User avatar
Tikigod
Posts: 152
Joined: Thu Apr 04, 2013 9:29 pm
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: Pathfinding accuracy rewrite

Post by Tikigod » Sat Apr 20, 2013 11:50 pm

SimoRoth wrote:There will be a lot of layers eventually. Not hundreds, but at least 5-10 by mid summer, this isn't a cube based world, but you will connect layers with ladder and lift shafts. :)
:o :o :o

Awesome!

Are there plans to have anything distinct available in lower layers that aren't found on the surface layer?

Now 16 I.M.Ps really does seem very little! :D
Violence is the last refuge of the incompetent - Isaac Asimov

My channel. Game recordings & old 3D art assets I've made.

User avatar
SimoRoth
Site Admin
Posts: 1106
Joined: Sat Jul 14, 2012 11:28 am
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: Pathfinding accuracy rewrite

Post by SimoRoth » Sun Apr 21, 2013 12:07 am

Tikigod wrote:
SimoRoth wrote:There will be a lot of layers eventually. Not hundreds, but at least 5-10 by mid summer, this isn't a cube based world, but you will connect layers with ladder and lift shafts. :)
:o :o :o

Awesome!

Are there plans to have anything distinct available in lower layers that aren't found on the surface layer?

Now 16 I.M.Ps really does seem very little! :D
Yes, I made the choice to have a few distinct layers over tonnes of empty boring ones. :)

vanatteveldt
Posts: 21
Joined: Mon Dec 10, 2012 9:56 am
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: Pathfinding accuracy rewrite

Post by vanatteveldt » Mon Apr 22, 2013 11:48 am

Well I think pathfinding is actually a major cause of "FPS death" of large fortresses in DF. However, DF easily has 200 dwarfs plus a couple hundred cats and dogs plus a hundred invaders on the map at the same time, so that is a lot more than the numbers Simon is quoting. I think one of DF's main problems is that they don't do any multithreading, even though pathfinding many different units is embarrassingly parallel, and I expect the same to hold for quite a big part of the simluation backend. Finally, there doesn't seem to be a good separation between the interface layer and engine, or at least Toady is unwilling to let people write a different interface layer on his engine (even though his interface is not exactly a prime business asset :))

From the people over het Clockwork Empires I hear they do full A* search, which I think is a waste, you can easily memoize some stuff, use corridors, and do beam search / cutoff, and the end result might actually be more realistic since people have no perfect pathfinding, but the programming work to come up with heuristics that save cost while looking realistic might not be worth the effort. You could have a unit store "routes" from A to B that have worked in the past, and continue using those routes 'out of habit' for a while even if a new road has been opened. It would be fun if a colonist would run to safety only to find out that the normal main corridor is actually collapsed when he gets there. In DF, all units immediately know the whole map.

What kind of search will Maia be using?

Also, I think that the graphics, simulation, and pathfinding parts are all pretty much independent of each other in the sense that perfect pathfinding 300 units in a 200x200x20 space will take a lot of time regardless of how or whether you will paint the results on a screen. The painting will presumably be mainly GPU work, while the pathfinding will mainly be CPU work in background threads.

User avatar
Tikigod
Posts: 152
Joined: Thu Apr 04, 2013 9:29 pm
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: Pathfinding accuracy rewrite

Post by Tikigod » Mon Apr 22, 2013 2:18 pm

vanatteveldt wrote:Well I think pathfinding is actually a major cause of "FPS death" of large fortresses in DF. However, DF easily has 200 dwarfs plus a couple hundred cats and dogs plus a hundred invaders on the map at the same time, so that is a lot more than the numbers Simon is quoting. I think one of DF's main problems is that they don't do any multithreading, even though pathfinding many different units is embarrassingly parallel, and I expect the same to hold for quite a big part of the simluation backend. Finally, there doesn't seem to be a good separation between the interface layer and engine, or at least Toady is unwilling to let people write a different interface layer on his engine (even though his interface is not exactly a prime business asset :))

From the people over het Clockwork Empires I hear they do full A* search, which I think is a waste, you can easily memoize some stuff, use corridors, and do beam search / cutoff, and the end result might actually be more realistic since people have no perfect pathfinding, but the programming work to come up with heuristics that save cost while looking realistic might not be worth the effort. You could have a unit store "routes" from A to B that have worked in the past, and continue using those routes 'out of habit' for a while even if a new road has been opened. It would be fun if a colonist would run to safety only to find out that the normal main corridor is actually collapsed when he gets there. In DF, all units immediately know the whole map.

What kind of search will Maia be using?

Also, I think that the graphics, simulation, and pathfinding parts are all pretty much independent of each other in the sense that perfect pathfinding 300 units in a 200x200x20 space will take a lot of time regardless of how or whether you will paint the results on a screen. The painting will presumably be mainly GPU work, while the pathfinding will mainly be CPU work in background threads.
The problem I found with storing known suitable paths from A to B, is the sheer number of permutations that come from what 'A' and 'B' are. It's not so much of a problem dealing with limited number of nodes on a flat 2D plane, but it very quickly escalates to the point where you're retaining information that has no application for very long periods of time.

One of the variations of the idea I've been trying (read as, it's mostly conceptual so far, and the overall practicality of it hasn't been properly tested yet) with my own A* pathfinding experiments to get more familiar with the application of the concept is to start off during initialisation generating the basic state information for each node, to determine what is open, what is minable/destructible and what is currently an invalid node (water, non-destructible terrain etc).

Each node then stores a value which represents its adjacent neighbouring nodes if they are open, another for those that could be mined, and a third for untested open tiles leaving all other tile nodes as entirely unknown to neighbour nodes.

To start with each neighbour open node is stored as untested.

When the first unit wants to then get from 'A' to 'B' across nodes not previously made use of, a slightly slimmed down A* search is then done using the valid node references and during the process the neighbouring nodes are shifted from untested to being treated as open, and rearranged based on which was ultimately the better option.

The second unit that may want to use part of the previous 'A' to 'B' route or all of it if it has the same origin and destination, will then go through a similar process but first attempting the last ideal node, and then that nodes last ideal and so forth until it determines the route is not working, then it will attempt the 2nd last ideal and so forth until it finds a route that is acceptable within a preset margin of deviation from a perfect route.

If the ideal findings of the second unit differ to that of the first unit that initially set the order, then the second units ideal node is then shifted up in order, or if it's already 2nd in order gets promoted to first.

This is repeated for each unit, with the idea being that common trends in pathfinding routes and direction will eventually after a small number of iterations form a structure of neighbour nodes that have a much higher probability of returning exactly the node the unit would want, or if not then it will during the 2nd iteration, leaving further iterations less common place and more for when you give a unit a specific order to go somewhere removed from general activity.


As far as nodes located in currently non-usable tiles that may eventually be passable (Mining a wall section), when a section is mined the node will 'call out' to its neighbours known to be opened, and then be moved to those nodes untested list.

When determining pathfinding, untested nodes will then take priority first when checking acceptable paths and then will be assigned its position in the existing structure of permitted nodes.


The idea still needs more fleshing out, and certainly isn't one I've yet fully tested to see if it trend activity even occurs as desired, would also definitely be better off trying to introduce a effective way to try and reduce the amount of reorganisation of neighbour nodes needed, without having to throw in more stored data for each node, it's also overlooking certain important factors such as:

* Existing units at a tile when checking validity, assuming you don't want dozens of units all walking through each other or ignoring the fact that 3 nodes ahead of them in plain site is a blood soaked axe wielding maniac screaming how he's going to kill the unit, and having the pathfinding logic tell your unit "Yep, the tile that guys standing on is perfectly safe. Go there".

* Also assumes that all open tiles have the same amount of room to navigate through, which would never happen as you would have doorways, hatches, equipment and all other kinds of objects that could be placed, though a similar process to changing from destroyable tile to untested but in reverse may work specifically for open placement of equipment.


But hell it's a idea based on my very first attempt at a crude primitive pathfinding system, so it's bound to be inefficient and have holes in. :)
Violence is the last refuge of the incompetent - Isaac Asimov

My channel. Game recordings & old 3D art assets I've made.

kevok
Posts: 22
Joined: Mon Apr 08, 2013 8:03 pm
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: Pathfinding accuracy rewrite

Post by kevok » Tue Apr 23, 2013 2:31 pm

vanatteveldt wrote:Well I think pathfinding is actually a major cause of "FPS death" of large fortresses in DF. However, DF easily has 200 dwarfs plus a couple hundred cats and dogs plus a hundred invaders on the map at the same time, so that is a lot more than the numbers Simon is quoting. I think one of DF's main problems is that they don't do any multithreading, even though pathfinding many different units is embarrassingly parallel, and I expect the same to hold for quite a big part of the simluation backend.
Which is why I recommended about 20 posts ago to try talking to Toady to get his pathfinding algorithm and multithread it. When you think about it, if DF can pull of moderate FPS while pathfinding for 250-300 different entities, shouldn't Maia be able to pull off hundreds of fps for only 25-30?
AMD Phenom II X6 1045T
Nvidia GeForce GTX 560
2x 4GB DDR3 1333MHz
Windows 7 x64

User avatar
Tikigod
Posts: 152
Joined: Thu Apr 04, 2013 9:29 pm
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: Pathfinding accuracy rewrite

Post by Tikigod » Tue Apr 23, 2013 2:45 pm

kevok wrote:
vanatteveldt wrote:Well I think pathfinding is actually a major cause of "FPS death" of large fortresses in DF. However, DF easily has 200 dwarfs plus a couple hundred cats and dogs plus a hundred invaders on the map at the same time, so that is a lot more than the numbers Simon is quoting. I think one of DF's main problems is that they don't do any multithreading, even though pathfinding many different units is embarrassingly parallel, and I expect the same to hold for quite a big part of the simluation backend.
Which is why I recommended about 20 posts ago to try talking to Toady to get his pathfinding algorithm and multithread it. When you think about it, if DF can pull of moderate FPS while pathfinding for 250-300 different entities, shouldn't Maia be able to pull off hundreds of fps for only 25-30?
Entirely different environments and use of pathfinding I would have thought.
Violence is the last refuge of the incompetent - Isaac Asimov

My channel. Game recordings & old 3D art assets I've made.

kevok
Posts: 22
Joined: Mon Apr 08, 2013 8:03 pm
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: Pathfinding accuracy rewrite

Post by kevok » Wed Apr 24, 2013 12:18 am

Tikigod wrote:
kevok wrote:
vanatteveldt wrote:Well I think pathfinding is actually a major cause of "FPS death" of large fortresses in DF. However, DF easily has 200 dwarfs plus a couple hundred cats and dogs plus a hundred invaders on the map at the same time, so that is a lot more than the numbers Simon is quoting. I think one of DF's main problems is that they don't do any multithreading, even though pathfinding many different units is embarrassingly parallel, and I expect the same to hold for quite a big part of the simluation backend.
Which is why I recommended about 20 posts ago to try talking to Toady to get his pathfinding algorithm and multithread it. When you think about it, if DF can pull of moderate FPS while pathfinding for 250-300 different entities, shouldn't Maia be able to pull off hundreds of fps for only 25-30?
Entirely different environments and use of pathfinding I would have thought.
From the picture, it looks like terrain is in large chunks and objects in small. If we do everything in small chunks, we can break each of the floors into hi-res passability maps. I would think this is where DF starts, as everything is already defined as passable or not passable. From there, we acknowledge each mover's current location and destination, and try to find the fastest way to get there. Assuming Simon doesn't care about the omniscient dwarf issue, the DF algorithm should still work well in this instance.
AMD Phenom II X6 1045T
Nvidia GeForce GTX 560
2x 4GB DDR3 1333MHz
Windows 7 x64

Post Reply
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Who is online

Users browsing this forum: No registered users and 1 guest