Print

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

[PartyBear]

Yeah, I knew the memory requirements were nutty, even though I didn't bother to actually calculate them (so thanks for that), but I liked the thought experiment anyway.

[Andeerz]

Me too, PartyBear!  For what it is worth, I am very appreciative of different strategies (no matter how obscenely implausible and practical they are) being presented if not for giving a solution, then for giving some much needed food for thought!  I am also very appreciative of well reasoned "tests" of such strategies as presented (though I'm not appreciative of arrogant delivery... not that my opinion really matters here ) by Draco18s.  Gives me and likely other readers of this thread some good stuff to think about... 

[NW_Kohaku]

Well, for myself, I think this is what makes me most pause and give thought:

If the maps never had to change, it would work well, but of course we can dig and build to drastically change the landscape, and to work perfectly, every single tile would have to recalculate its map every time you did something like lock a door or dig a tile, which would take a very long time.

If I'm going to argue for dynamic hierarchical map generation, then that means that the system will need to react quickly and with little need to recalculate based upon a door being locked (or denying access to animals), and the best way to do that would be to make doors a node all to their own.

Doing this would mean locking a door would simply mean disconnecting that door's node from everything else. 

I don't like it, but making doors nodes leads to the Granite26-suggestion of reshaping the nodes based upon where the doors are as a matter of course.  (Although I still think a more dynamic system is necessary so that it isn't all loaded on door placement, and there should still be a recognition of "vertical hallways" like stairwells.)

More dramatic changes (like channeling out a hole in the floor) would still require a recalculation, but if you start from "local cells", and only work on their relation to other local cells, running things through a "highway system", then you can hopefully dramatically cut down on how many recalculations you need to do on changes to the map, just to local connectivity, and whether you can still make the assumption that different modes of transport can still path through a given cell.

Otherwise, there might be a need to not cut out all the redundant pathways in a Hierarchical AA* mapway, since a blocked path would necessitate looking for detours, but you should still be able to maintain the "highway" map for a fairly low overhead compared to the cost of the current connectivity map. 

[Artanis00]

Python stuff ewww .

Careful, thems' fightin' words.

Faux offense aside, what don't you like about it? (PM me or something, no need cluttering this thread with a programming language discussion, too!)

People at work saw my Algorithm book out and had memories . Learning is important part of my job. I usually remember what I learn but I only think we covered half that book .

Least you got a book. I have... Wikipedia?

So I looked up what IP routing was doing (reasoning that since most of the graph is unknown before-hand there's some voodoo magic going on), but it turns out it tends to use the same methods we've been looking at... with the added benefit of being highly distributed, so each node can store routes to common destinations.

I don't like it, but making doors nodes leads to the Granite26-suggestion of reshaping the nodes based upon where the doors are as a matter of course.  (Although I still think a more dynamic system is necessary so that it isn't all loaded on door placement, and there should still be a recognition of "vertical hallways" like stairwells.)

You have got to find a better term for that.

I'm starting to think that just about all can be done is to split the pathfinding code out into a child thread so at the very least it doesn't block the game.

Aside from doors, don't forget burrows. These will slice up any 'rooms' that are created quite easily. Imagine your poor dwarf being told by the node-traversal algorithm that he can get somewhere (because his node connects to that node, obv., optionally through some intermediary nodes) but he can't get to the exit of his node that leads to that path, since it's not in the burrow. Now our dwarves act like cats trying to path through a pet-locked door, too...

[Starver]

Aside from doors, don't forget burrows. These will slice up any 'rooms' that are created quite easily. Imagine your poor dwarf being told by the node-traversal algorithm that he can get somewhere (because his node connects to that node, obv., optionally through some intermediary nodes) but he can't get to the exit of his node that leads to that path, since it's not in the burrow. Now our dwarves act like cats trying to path through a pet-locked door, too...

As pointed out recently (if not this thread, then somewhere else, in which case apologies and just take this as information instead of re-telling), Burrows aren't "you may only step on these tiles", but are mechanisms to say "if the item you're looking at isn't in the burrow(s) you're in, forget about that job".  If the target location (tile with a bit of rock, or place to eventually put that rock[1]) is inside the burrows for a given agent, that agent will gladly walk across non-burrow tiles to get from the first bit to the last, exactly the same as if there was no burrow, just the same old pathing algorithm with good reason to send them that way.


And, regarding the "having no way to tell that the pressure plate will allow travel" issue, whoever it was now who responded directly to that last post of mine, I'm also very much of that opinion.  I was just trying to break the problem down into various different solutions.  Primarily "always have a quick route" vs "always strive for the best route", but with additional 'add-on' items of having both Artificial Stupidity and more advanced Architectural Awareness that could be tacked onto either solution (or a happy medium that doesn't go so slowly, and also does tend to hit the 'best' route 7 or 8 times out of 10, so giving the players the balance of speed and accuracy they crave.

Both the AS and the AA would always add something to the load (the first may have to prune omnisciently-known details from the master-map, whatever that might contain, according to whether the agent involved is supposed to be ignorant of them; the second would need a more comprehensive route-finding programme with at the very least a limited 'T'-dimension on top of the current X,Y,Z dimension being examined for viable paths), so they're more speculation.  Although I think at least the AS could be done, in a more shortcutted way, yet still allowing the agents to exhibit obvious ignorance until new paths are learnt.  AA is a bit further out there.

Prior to that I'd really rather like instead to have a net of connections which has "fly", "climb short walls", "jump gaps" and even "bridge a gap" flags (or counters, e.g. with a limited number of bridging ladders available to an invading squad) which allow overlapping node-maps that represent better paths for particular types or quality of agents moving across the map, and explores the possibility of the defences-in-depth (which I currently establish purely out of moral/aesthetic reasons) to become both useful and even needed to be further refined to proof them against the as yet unencountered enemies with even more tricks up their sleeves than I can currently imagine.



[1] Although I think that bit of code is faulty (or could be written better), the number of times it appears to want to start a job but then has to spawn a notification complaining that the destination is unreachable.  If it was unreachable, you shouldn't have even considered picking up that stone that you'd have to dump somewhere not within your current set of burrow zones...

[NW_Kohaku]

I thought burrows simply cut off where dwarves were able to take up tasks, but they could path through areas outside their burrows?  Basically, if you told a dwarf that they were part of a small burrow, and they started outside of that burrow, they would have to have some way of pathing to get into that burrow to even start with. 

Doing a pretty quick test, if you make a burrow that has a few "islands" of burrow area with a gap of non-burrow area, dwarves will go through areas outside their burrow to reach areas that are inside their burrow.  Burrows have no effect on pathfinding code, just upon what jobs or items they can "see" to take up.

Anyway, suggesting multithreading pathfinding is very, very common, and Toady has pretty clearly said he isn't interested in it.


ah, nevermind, heavily ninjad.

[Starver]

ah, nevermind, heavily ninjad.

But you actually tested it (I just went off memory of past experiences), plus explained it far more succinctly.

I actually prefer your reply, but it might be considered petulant to now delete my own.

[NW_Kohaku]

No need to delete it, it doesn't harm anything being there...

Prior to that I'd really rather like instead to have a net of connections which has "fly", "climb short walls", "jump gaps" and even "bridge a gap" flags (or counters, e.g. with a limited number of bridging ladders available to an invading squad) which allow overlapping node-maps that represent better paths for particular types or quality of agents moving across the map, and explores the possibility of the defences-in-depth (which I currently establish purely out of moral/aesthetic reasons) to become both useful and even needed to be further refined to proof them against the as yet unencountered enemies with even more tricks up their sleeves than I can currently imagine.

That's actually a part of the Hierarchical AA* type of code - you can store pathways, and include flags for what sorts of movement types are allowed to use those pathways.  You might store a long path for regular walkers, but have a short path for fliers across a chasm.  It's just that node's connection carries a "fliers only" flag. Or, you can store a "can jump a single gap" or "can climb one z-level of wall" type of pathway, instead. 

Oh, wow, I just thought about how horrible a mess the digging/tunneling enemies pathfinding code will be without having some sort of code built specifically around allowing that sort of thing to occur.  A* is just not really built for "you can ignore one otherwise impassible wall if you want to" types of pathfinding.

[Starver]

Oh, wow, I just thought about how horrible a mess the digging/tunneling enemies pathfinding code will be without having some sort of code built specifically around allowing that sort of thing to occur.  A* is just not really built for "you can ignore one otherwise impassible wall if you want to" types of pathfinding.

I see it as digging-capable ground-hugging squads (much as bridging-capable squads, also without intrinsic flight) arriving with the inherent ability/tendency to route across 'N' tiles of otherwise unwalkable terrain.

A version of the HAA* which allows path-search to tunnel through 'N' tiles of earth, or cross 'N' ditches (but not across a single ditch of width 'N', unless N==1 of course ) could say "Ah, diggers, you may set about tunnelling through those tiles, and you bridgers can set about bridging those ditches...  But no more!".

And then it gets a complicated mess when an attacking squad actually has so many bridging ladders (courtesy of suitably equipped squad members) and so much willingness to dig through so much ground (courtesy of some sappers, whose energies may sap, and possibly after only N/2 tiles of various rocks instead of N of soil) and both hierarchies have to be examined, with not just a single "distance from source" (or "to destination") flag per examined tile, but one for each "used X bridges, used Y digging efforts" to reach them.

Still, I think it could be done.  I've still got some of my unpublished experimental scripts (from when the Other Pathing Thread was actively running) sitting around on either this machine or the one upstairs, and I'd sort of started hacking this ability into one particular one.  Maybe I'll dig up what I've got and get it actually working.

(Certainly, they're not as quick as their non-complex plain-old-A* companions, but as I hadn't really tried any of the obvious optimisations it's possible I can make them not too much slower, and with additional partial-path caching added in they could be something worthwhile (converted from my test-script format into something properly executabley encoded, of course).  I must get my finger out, this time round.)

[Artanis00]

I just did    but the output is really long with hex but if you are well versed in binary you could almost see the maze  .
example:
http://niseg.0adz.com/test_maze.html?maze=0080008000800000FFF7008000000080EFFF008000010080FFF7008000000080

I can change that to B64 -the conversion is the same just 6bits at a time instead of 4 (did it on a damage calculator for infantry online). B64 would be 43 chars instead of 64. I might add some run length encoding into it but I think it's too much trouble for this narrow purpose (We aren't trying to rewrite DF in JS ). 

My script now (also) creates a link to that page with the maze (not really a maze, but whatever) properly encoded.

Still available at the same location: https://gist.github.com/876876

Also, DF in javascript would be epic, and should be considered.

[ullrich]

That wave front thing sounds like Breadth first search from the destination.

Wavefront and Breadth are not the same, wavefront doesn't actually store nodes (it doesn't need to keep a closed set) so its more efficient.

Basically you have 2 extremes memory and processing speed:
1) Wave front = max speed, massive set and static memory (you don't generate new pathing maps EVER, they are all generated already and you simply change the maps value as the terrain changes). Also it does not need to re-expand the entire map on terrain transition as walls/un-walkable squares get a value such as -1 that results in it getting ignored and will prevent further expansion.

Alternatively just 1 single pathing map could be kept and the values re-propagated for each creature, while this sounds really bad, and in terms of nodes is higher it uses a much simpler expansion logic than breadth first or A* so potentially expanding say 2x as many nodes could be done faster in wavefront than A*, especially in dead end cases since wavefront dead end cost is minimal.

2) A* = best memory usage (min), decent speed.
All these really fancy algorithms discussed in this thread will likely take longer to run and get functioning properly if made automatic then a simple heuristic improvement would result in improvement of the current manhatten A*. As I said previously in this thread the cross product manhatten heuristic can provide massive node expansion reductions by adding tie-breaking to tiles:

	End in a Room, 1 entrance, close.	Opposite Side of Map, multiple paths.	Opposite Corners of Map, multiple paths.
Breath-First	376	250	488
A* (Manhattan)	77	81	340
A* (Vector)	48	72	117

From this we get 62.3%, 88.9%, 34.4% of the number of nodes generated to complete the path.

[Niseg]

Python stuff ewww .

Careful, thems' fightin' words.

Faux offense aside, what don't you like about it? (PM me or something, no need cluttering this thread with a programming language discussion, too!)

No offense intended I am just too used to C-like languages . I saw someone at work that uses awk - I was surprised but it does have its uses.

Least you got a book. I have... Wikipedia?

Its a pretty famous book most CS major know.  I learned complexity of algorithm with it . It's big and white and it's also very expensive ( I think it cost me like 80$).

So I looked up what IP routing was doing (reasoning that since most of the graph is unknown before-hand there's some voodoo magic going on), but it turns out it tends to use the same methods we've been looking at... with the added benefit of being highly distributed, so each node can store routes to common destinations.

Ip routing is a pretty simple system where the network is divided into segments and the router is in charge of sending them foward. the clients are pretty simplistic and don't do much routing while routers generally know "who know how to get to the destination" . The paths are also pretty short. It's also kind of highways and intersections.


Anyways my idea is based on the fact that  pathing algorithm has an  exponential worst case complexity (k^N) which are generally worst than N^k. There is still a way to reduce the runtime by converting a problem into many smaller problems:
consider constant a which is room size and variable x number of rooms
if complexity N= ax  and your complexity is k^N if you can convert the problem from k^(a*x) to k^x+x*k^n you'll have a better runtime . This basically means you can convert the problem to x room traversal + x problems of moving from one room to another.

You are still using A* but you say "what happens when a room changes ?" you don't really need to regenerate the whole map. It's like redrawing the map of the USA when Florida connect two roads. The only one that's affected is the local area ( neighboring towns). If for example Tampa is effected and you want to get from Los-Angeles  to Tampa most of your way  would be identical except in the end.. My solution doesn't require you to know the "paths" from one room to another it just requires you to know if such path  exists. This gives a dwarf a whole lot of freedom of movement even though he's  using a "map".    If a dwarf or whatever finds out some room have been blocked he'll then update that room and its neighboring rooms and find a new path.

[Mohican]

I didn't read the whole thread so excuse me If someone already said what I'll say.
The current most efficient pathfinding method use "navigation mesh". This method is generaly used in non-tile based map, but only because it's easier to use each tile as a node , not because it's more efficient. here are the basics:

-First we "cut" the map in convex polygons (rectangle in our case)
-We represent this polygons with a graph , each polygon is a node, 2 nodes are connected if the polygons they represent are touching. ( so a node will often represent more than 100 tiles)
-We use A* on this graph, this will give us the list of polygons our path go through.
-Then we use the funnel algorithm (here is a link http://digestingduck.blogspot.com/2010/03/simple-stupid-funnel-algorithm.html )

At this point we should have a set of points where our dwarf just need to go in straight line between each points. But what is a straight line between 2 points in tile based map? Well , we could define it as going in diagonal (starting form the 1st point) until reaching one of the two coordonates of the 2nd point , then going in "true" straight line (horizontal or vertical) for example.

IF the map was static , I think this method could easily be 100 times (depending on the fortress shape) faster than the actual method.
But the map isn't static, it's true, but the map is changing only 1 tile by 1 tile. We could create a function that will add a node to our graph each time a dwarf dig 1 tile, and merge 2 rectangles if they share an entire side, this function should also check each time a door is closed or a wall build if there is change to do in the graph. I don't think this function is very hard to make, and probably not very CPU expensive. So I have hope this method could still be at least 10times faster than the actual method.

Each part of this method is very easy , and shouldn't take more than 100 lines.
There is tons of ways to represent a graph (http://en.wikipedia.org/wiki/Graph_(data_structure) give the most common)
I hope toady will make something about it , his game is fucking great , if he doesn't want to dive in the pathfinding, maybe if he could just give the format he uses to represent the map and coordonates , and the format he wants for the output path , I'll be glad doing this for him.
Forgive my poor english.

[Artanis00]

-First we "cut" the map in convex polygons (rectangle in our case)
-We represent this polygons with a graph , each polygon is a node, 2 nodes are connected if the polygons they represent are touching. ( so a node will often represent more than 100 tiles)
-We use A* on this graph, this will give us the list of polygons our path go through.
-Then we use the funnel algorithme (here is a link http://digestingduck.blogspot.com/2010/03/simple-stupid-funnel-algorithm.html )

One minor tweak: instead of convex polygons, convex polyhedrons (rectangular prisms). Under normal circumstances, there'd be no difference since most forts are mostly 2d floors with very few 3d rooms, but if it considers vertical space first, it should end up with nodes for uninterrupted stair columns (as well as air space, which may be useful later for flight). May want to limit polyhedron size so that any single node doesn't cover half the z level or every bit of open space above the tallest peak, however; Perhaps to map block size, which is some 16 tiles, so 16x16x16 at worst. That would also limit rebuilding the nodes.

[Mohican]

-First we "cut" the map in convex polygons (rectangle in our case)
-We represent this polygons with a graph , each polygon is a node, 2 nodes are connected if the polygons they represent are touching. ( so a node will often represent more than 100 tiles)
-We use A* on this graph, this will give us the list of polygons our path go through.
-Then we use the funnel algorithme (here is a link http://digestingduck.blogspot.com/2010/03/simple-stupid-funnel-algorithm.html )

One minor tweak: instead of convex polygons, convex polyhedrons (rectangular prisms). Under normal circumstances, there'd be no difference since most forts are mostly 2d floors with very few 3d rooms, but if it considers vertical space first, it should end up with nodes for uninterrupted stair columns (as well as air space, which may be useful later for flight). May want to limit polyhedron size so that any single node doesn't cover half the z level or every bit of open space above the tallest peak, however; Perhaps to map block size, which is some 16 tiles, so 16x16x16 at worst. That would also limit rebuilding the nodes.

Yes, you are right, using polyhedrons would greatly improve pathfinding if it comes through a hundred stairs. Though for the size limitation I don't realy see the utility, I think there will still be the same amount of nodes rebuilding even with a size limit , or maybe I am missing something?