One could even try to to turn it into a fractal map where you have larger hub nodes that feed smaller capilary pathfinding nodes, which would be better for pathfinding in labyrinthine dwarf tunnels, but poor for pathfinding in open areas.
You can make large, open environments even "inside", though. Some people even make large hallways consisting of nothing but up/down stairs so that dwarves can "fly" by moving in every possible direction, since that optimizes pathfinding for A*.
But even with the a* algorithm, you could have a node in every second square instead of every single square. That would be faster whatever algorithm you use.
Well you would still be able to move orthogonally, but it will be able to assume that there's a walkable space between 2 connected nodes.
I'd expect it would really help with workshops, though, if you have a "prefer items from this stockpile" command that would tell workers to only search for the materials in one particular stockpile before they do a general map search of every single item of that type in the entire fortress, and compare how to path to each one.
Currently the pathfinding is like an amnesiac autist: do everything step by step, include every little detail, and repeat it every time you have to go somewhere.
I'd expect it would really help with workshops, though, if you have a "prefer items from this stockpile" command that would tell workers to only search for the materials in one particular stockpile before they do a general map search of every single item of that type in the entire fortress, and compare how to path to each one.
I don't think the game paths to each item in that case. It finds the closest item by Cartesian distance and then paths to that one only.
every square is a node, it isn't stored as a graph though. It is stored as an array of node entry costs IIRC. Connectivity between nodes is implicit from adjacency.
Wouldn't storing pathfinding results for "most common paths" lead to a massive consumption of memory, though? Not that having an ability to trade processor time for memory space is a bad thing, but it can potentially exchange one problem for another if you have enough creatures walking around the map.It's possible to play around with the storage place. If you we're able to link stockpiles to workshops (though IMO stockpiling and workshop tasks could be both optional functions for a room, but that's another matter) then that path could be stored in the workshop. The bedroom to staircase could also be stored at the room's level. I expect these paths to be rather short anyway, but searching a bedroom starting in the storage room area, finding a staircase, and then searching on towards the right bedroom is much, much more CPU intensive that searching from the storage room to a known central staircase, and then retrieving a stored path from the staircase to the room.
I'd expect it would really help with workshops, though, if you have a "prefer items from this stockpile" command that would tell workers to only search for the materials in one particular stockpile before they do a general map search of every single item of that type in the entire fortress, and compare how to path to each one. You could even store the pathfinding from workshop to stockpile and back, which I'm sure is THE most frequent pathfinding function you perform.
That's what I mean. Let them use conceptual heuristics, gaining speed at the cost of accuracy. I'd rather have my dwarves make a detour now and then (or get lost) than cut my FPS in half. There's always the option to fall back on the thorough, standard way to do things instead of shortcut.Currently the pathfinding is like an amnesiac autist: do everything step by step, include every little detail, and repeat it every time you have to go somewhere.
It's a computer program. Computers can't generalize, at all, ever. They must perform the repetitive, excessive detail, tasks every time because that's how computers work. The only way to skip code is to be less accurate or find some way to infer the data without looking at it (i.e. a process that takes less cycles but comes to the same result, such as "that tile is a food stockpile tile" skipping the check that asks if each item in that tile is a stone or not*).
*There could be a stone in that tile, but odds are there isn't.
It's a computer program. Computers can't generalize, at all, ever. They must perform the repetitive, excessive detail, tasks every time because that's how computers work. The only way to skip code is to be less accurate or find some way to infer the data without looking at it (i.e. a process that takes less cycles but comes to the same result, such as "that tile is a food stockpile tile" skipping the check that asks if each item in that tile is a stone or not*).That's what I mean. Let them use conceptual heuristics, gaining speed at the cost of accuracy. I'd rather have my dwarves make a detour now and then (or get lost) than cut my FPS in half. There's always the option to fall back on the thorough, standard way to do things instead of shortcut.
*There could be a stone in that tile, but odds are there isn't.
The pathfinding could also treat the z-level differently (which makes sense, dwarves can't change z-levels without stairs or the like): check first if the destination is on the same level; if yes, pathfind only on the level; if not, pathfind to a staircase instead. That would make 90% of routes easier, and 5% more difficult, but it's always possible to revert to the standard, cpu-intensive but almost infallible pathfinding.
I know, but that's not the main reason why the game lags, the game lags because every time a stonecrafter at a workshop wants to find something, he has to access a list of every single stone in the fort to then test cartesian distance of each one to find the closest, even if there are tens of thousands of stones to choose from.
Or just shut off all your workshops, and let dwarves idle.
I personally became very well acquainted with the phenomenon when I altered the trade caravans to have enough cargo capacity for the elves to bring in about 20,000 items onto the map at once, which instantly lopped my FPS down to about a fifth of its previous rate. Yeah, sure, that was with temperature, but it wasn't all temperature, it was my weavers looking at all that rope reed from across the map every time they went looking for something else to perform their jobs with.
I'd have to ask how much stone there is laying about in the fortress you tested this on, for starters, on the inventory screen. I'd also have to ask how far away they were going to get it. Also, what the idlers were actually doing.
If, as is your hypothesis, there is negligible impact on the time spent on populating lists of objects for the purposes of finding one to pathfind to, then the framerates should be the same - having it actually drop for idling implies something else is suddenly taking up their processor time.
Staircases in general don't move that often, so if you can identify the big ones, you can use their location again and again without pathfinding again. The drawback is that your dwarves will act a bit confused when, for example, the staircase collapses... but that only adds to the verisimilitude - when a staircase collapses, it does confuse people.The pathfinding could also treat the z-level differently (which makes sense, dwarves can't change z-levels without stairs or the like): check first if the destination is on the same level; if yes, pathfind only on the level; if not, pathfind to a staircase instead. That would make 90% of routes easier, and 5% more difficult, but it's always possible to revert to the standard, cpu-intensive but almost infallible pathfinding.
How do you know where staircases are, if not by pathfinding?
Actually, I'm more concerned about the assumption that all players will make mostly 2-dimensional forts with rare stairwell access. What about players who purposefully make their fortress more vertical? I tend to make things fairly vertical to compress my fortress into being as spheroid as possible whenever I'm not going for more elaborate fractal designs. It's more efficient that way.Ah, but dwarves are restricted by gravity and walk on the x-y plane. They don't walk along the y-z or x-z plane. In addition, workshops, stockpiles and the like can't be built vertically.
Why should a change in the axis you move along change the way that the game calculates how to get from one point to the other, when it basically is as easy (if not easier) to move vertically than horizontally?
You should look at this thread, at the very least:
http://www.bay12forums.com/smf/index.php?topic=43265.0
and look up the A* and manhattan systems to understand their methods.
| End in a Room, 1 entrance, close. | Opposite Side of Map, multiple paths. | Opposite Corners of Map, multiple paths. | |
| Depth-First (not optimal) | 78 | 31 | 81 |
| Breath-First | 376 | 250 | 488 |
| A* (Euclidian) | 163 | 94 | 380 |
| A* (Manhattan) | 77 | 81 | 340 |
| A* (Vector) | 48 | 72 | 117 |
DF isn't using Manhattan distance.
It is using Max(|x1-x2|,|y1-y2|,|z1-z2|).
If it was using Manhattan then a mason workshop making blocks in a quarry would clear out a diamond-shaped area. Now it clears a square/cube area.
I just tried this out with a community fort from the forums. I turned off all labors except stonecrafting and built enough workshops for everyone, then paused and put repeat rock craft jobs in each one. Then I duped the save and started up two copies of the game and assigned each to its own core. I used Dwarf Therapist to disable all labors in one game, then unpaused both.
Not sure I understand the cache point; both processes' cores were pegged.
What about player-created paths? Not traffic designations, but set point A to point B paths that creatures can incorporate into their calculated paths. Only the player actually understands his or her fort's layout well enough to optimize pathfinding within it. Or optimize it for aesthetics so they'll actually use the nice paved roads, or if the player wants the manic little beard transports to be sure to wander past all the nice calming statuary.
I thought that was the point of traffic designations? How would you go about doing that without traffic designations?
You still have to figure out which "waypoint" is nearest to both the dwarf and the destination, which is an NP-hard problem.
I like optimizing for rooms. Every area surrounded by doors is a room, node map concentrates on room connectivity, pathfinding is just to the next room. (each room contains traverse costs).
Recalc your zones when digging, but only the affected ones. Same with new doors
You're missing a couple of crucial things.
It's not the memristor function that solves the maze. Even with ordinary resistors, the current would find the best path(s). All the memristors do is store that path so that it's easily readable.
And there's the rub. While the work the memristors do is indeed simple (it's a sort of integral or sum), that's neither here nor there. What's needed is to solve for the current through the maze. Nature, being massively parallel - here basically every valence electron is doing computation for you - does it easily. Doing it in software would be hellish, as you'll appreciate if you've ever tried to figure the current through a complex parallel-and-serial network of electronic components.
...that said, this does have potential in hardware. Perhaps specialized maze-solving hardware will be available; fast 4-to-4, 8-to-8, 10-to-10 or 26-to-26 grids with configurable connection costs rated at "solutions per second"... that would probably end our pathfinding troubles once and for all!
I hate you. xkcd is drawn by a lazy asshole. It is not a good comic.
...O...
...O...
...O...
OOO+OOO
...O...
...O...
...O...
I should note that the paper didn't construct a physical network of memristors and instead constructed a simulation (not to mention asserting that such an "algorithm is superior to any existing maze solving methods", I don't know how this measures against pathfinding, though), but the idea of a a physical chip to do this it attractive. Why the small numbers though? I can't find sizes for current memristors, but they're not going to hit consumer market in such a chip if they are macro scale, so by the time one is made we should be able to fit some hundreds, if not thousands, on a chip, even accounting for infrastructure effecting walls and result reading.
Crafty players already place doors over bedrooms (regardless of how many occupants they have) and workshops, so that moody dwarves, thieves, wild animals or riots can be contained by locking a couple of doors. Low framerates would serve as a reminder to do so.
...
I think node-based pathfinding is a great way to make pathfinding as a whole work better, but either make the computer figure out where the nodes are by itself, or by giving the player an ability to designate, in some hybrid of burrow and traffic-zone-style, the nodes themselves.
Constructs that are physically built for physical purposes should not have meta-game exploit purposes.
I disagree NW...
1: Using stairs and doors to optimize pathfinding isn't meta, the pathfinder is simply recognizing them for what they are. Barriers to separate contiguous areas. Their effect is the same in game as it is for the player.
2: Optimization of processor time doesn't yield indeterminate solutions. You are findind the answer faster, not finding a better answer. Since df is turn based, there is no problem with that.
3: Players already do ridiculous things to speed up pathfinding, from restricting dwarves to their rooms to laying out traffic zones to killing and skinning hundreds of cats a year. Putting doors up to separate areas hardly seems worse.
Besides, I don't think 'use doors to separate areas' is really that onerous of a restriction.
So you don't have a front door to your fortress and have the whole fort on one level?
3: Players already do ridiculous things to speed up pathfinding, from restricting dwarves to their rooms to laying out traffic zones to killing and skinning hundreds of cats a year. Putting doors up to separate areas hardly seems worse.
3: Players already do ridiculous things to speed up pathfinding, from restricting dwarves to their rooms to laying out traffic zones to killing and skinning hundreds of cats a year. Putting doors up to separate areas hardly seems worse.
To put this bluntly: A fort that doesn't build doors or butcher stray cats at all should have just as many FPS as a fort that does.
This isn't game play or meta, but proper game design. The only reason butchering cats and building doors everywhere is necessary right now is because it's a workaround for a bug that cripples game play.
Why are you so upset at the thought of the processor thinking of a room as something different from what you think of a room?
That's all I'm seeing. No argument that it would behave worse for you, just that what I'm calling a room doesn't match your definition, as if what you (or I, or any other meatbag) thinks of as a room matters in the slightest for pathfinding.
Who cares if the pathfinder cuts your Escherian construction into 3-4 rooms in the.background?
I've explained why (I think) arbitrary nodes are a bad idea.
It's also naive or disingenuous to claim that blocks of stairs, lines of ramps, etc couldn't be handled as a single entity, seeing as we've already covered that case.
That's pretty much what we've been talking about. The hard part is coming up with how to do the nodes in a way that will support outdoors, inside a fortress, in a cavern, etc.
That's pretty much what we've been talking about. The hard part is coming up with how to do the nodes in a way that will support outdoors, inside a fortress, in a cavern, etc.Right. The node idea has been discussed quite a bit, both here and in the Pathfinder Project. But I think the idea of routing tables is new(ish). I'm actually curious how that'd work in practice. I may throw together a proof of concept. :)
You need to deal with mazes,* large open spaces, spaces with 1 entry, 2, and 20.Large open spaces seem like they're not really a problem. Set aside a tunable parameter for how large of groups actually will form and divide it into a grid of that size. Up to the (unlikely) possibility of including the entire outside as a node in a region where your fortress is entirely underground with minimal wildlife that needs pathing.
1. create an data structure with 256X256 block of the map on each z levelWhy on each z-level? As NW_Kohaku was talking about, it would be nice to treat the z-axis equivalently (or at least weighted) to the x and y for people that build vertically. (And I'm sure he's not the only one).
2. for each block in the map recursively split recursively into 4s according to number of directions you can travel.So... a quad tree (http://en.wikipedia.org/wiki/Quad_tree). :)
5. add update schemeThis is the hard part. How/when does this run? This has to be more efficient then the current pathfinding we have, otherwise it's not worth changing.
2. for each block in the map recursively split recursively into 4s according to number of directions you can travel.So... a quad tree (http://en.wikipedia.org/wiki/Quad_tree). :)
5. add update scheme
This is the hard part. How/when does this run? This has to be more efficient then the current pathfinding we have, otherwise it's not worth changing.it's not really hard if you go through the rules of how you make eache zone like a zone has to have 7 (open area ) or more dirrections or 3 or less (path ,intersection,dead end). you can either update as dwarves go along it or run zone updates in the background.
#########
###+X+++#
O##+###+#
+##+###+#
++++++++#
#########
A . B .
##.###.####
##.#+X.+++#
O#.#+#.##+#
....... C
+#.#+#.##+#
++.+++.+++#
##.###.####
D. E .
. separator
O start position
X end position
# wall
+ floor
So, this article on memristors and maze solving (http://www.technologyreview.com/blog/arxiv/26467/?nlid=4196) came across my feeds a few days ago. The paper it reports on is a surprisingly easy read (and the pictures at the end are enlightening), so consider reading it.[...]
This isn't game play or meta, but proper game design. The only reason butchering cats and building doors everywhere is necessary right now is because it's a workaround for a bug that cripples game play.
This isn't game play or meta, but proper game design. The only reason butchering cats and building doors everywhere is necessary right now is because it's a workaround for a bug that cripples game play.
I'd just like to s/bug/condition/ in this statement.
While it may not be the absolute optimal method (as often argued) it's a consequence of the current condition of the DF universe. You might as well say that the Creator created a 'bug' that one cannot travel faster than light in our own universe.
And despite my machine being not particularly the best (worldgen and fort-save times are far longer than I'd like) I can't honestly talk about "crippling". I tend to run complex forts (without any particular nod towards meta-gaming the known pathing optimisations that are possible) and the number of free stones (not locked away) is often large in my various midi-projects (verging on mega-). Perhaps my expectations aren't high enough. Perhaps the general slowness of other aspects (unnoticed by me, as I'm used to it) means that I'm happy with the slowness of path-recalculation.
To play a more accurate analogy, it would be as though time itself slowed down when too many people gathered in a city. Unlike the speed of light issue, which we can definitely measure in-universe, such an effect would be as unmeasurable to us as the pathfinding slowdown would be for our simulated dwarves.Even before I read the second sentence, I was going "well, maybe it is like that..."
I should be able to mod my dwarves to have [SPEED:-1], which would cause them to appear at their destination before they left.Um, no. DF works linearly, and while there's no technical reason why Toady could not allow instantaneous travel (one blink, at location A; next blink, at location B... or possibly same blink disappearing from A even while appearing at B) finding an agent at location B prior (even by one blink) even to the decision to leave location A is not possible, as is.
To be completely honest myself, I tend grow bored of a fort shortly after initial setup; right when I start plotting out the MOST EPIC FORTRESS EVER CONCEIVED™ and remember that building large (complex and therefore interesting) structures is still a PITA, and thus am rarely affected by this myself.
##################
#++++++++++++++++#
###########+######
#+++#+++#++++++++#
#+++++++#+++#++++#
#+++#+++++++#+++X#
##################
##################
#++++++987666789+#
###########5######
#+++#+++#76543222#
#++++++9#765#3211#
#+++#++98766#321X#
##################
You'll notice as I you get farther away from the X you get bands of numbers which show the distance between X and that spot. After inspecting the search steps you can see choke points at 4 and 8 and one at 5 which is harder to find . Those are generally
oops kinda finished it. They are good starting point and splitting points.You'll notice as I you get farther away from the X you get bands of numbers which show the distance between X and that spot. After inspecting the search steps you can see choke points at 4 and 8 and one at 5 which is harder to find . Those are generallyoops kinda finished it
You forgot to finish your thought, there...
Anyway, the problem with a breadth-first search like this is that every time something like water flows over the area, a door is locked, or someone channels a floor, you'd have to do another breadth-first search. That's painful.
The idea is not to replace pathing with BFS it would be silly. BFS was chosen in order to join nodes into a region. the depth of the search is gonna be limited and it would only require changes when a path is blocked off or things like that then all you'll need to do is check if a path still exist from the region affected to its listed neighboring regions.
Another optimization i can think of is improve heuristic function runtime. I once had a trick to find a decent rootfinding guess ( I totally avoided rootfinding and used the guess ) my guess consists of counting leading zeros and them shifting the number in half. In general I would generally avoid the sqrt in general the multiplication is bad enough.
They don't use sqrt right now - as far as I can tell, they just functionally use the largest of the three distances, x, y, or z. Since diagonals are free, 3 spaces directly to the east and 3 spaces east and 3 spaces north are the same distance away, 3 spaces.
They don't use sqrt right now - as far as I can tell, they just functionally use the largest of the three distances, x, y, or z. Since diagonals are free, 3 spaces directly to the east and 3 spaces east and 3 spaces north are the same distance away, 3 spaces.
I thought I remembered someone verifying that diagonal movements were weighted correctly and took sqrt(2) times as long as straight moves.
01... 0.... 0.... 0....
..2.. .12.. .1... .1...
...3. ...3. ..23. ..2..
....4 ....4 ....4 ...34
A####
# #
1+ #
2+ +4
3+ +5
# +6
# #
####B
They don't use sqrt right now - as far as I can tell, they just functionally use the largest of the three distances, x, y, or z. Since diagonals are free, 3 spaces directly to the east and 3 spaces east and 3 spaces north are the same distance away, 3 spaces.
I thought I remembered someone verifying that diagonal movements were weighted correctly and took sqrt(2) times as long as straight moves.
Edit: Diagonal movement is weighted correctly (http://www.bay12forums.com/smf/index.php?topic=30026.msg913704#msg913704) when it takes place, but the A* heuristic is Manhattan distance (sum of distance rather than max).
Unfortuantely, I don't see anything in there talking about any proof that moving diagonally takes 1.4 times as long as moving horizontally, especially since DF movement diagonally does not have any evidence of moving slower than horizontal movement. I'd have to ask G-Flex if he still believes that, and if he has evidence of that statement.
What about player-created paths? Not traffic designations, but set point A to point B paths that creatures can incorporate into their calculated paths. Only the player actually understands his or her fort's layout well enough to optimize pathfinding within it. Or optimize it for aesthetics so they'll actually use the nice paved roads, or if the player wants the manic little beard transports to be sure to wander past all the nice calming statuary.
I thought that was the point of traffic designations? How would you go about doing that without traffic designations?
What about player-created paths? Not traffic designations, but set point A to point B paths that creatures can incorporate into their calculated paths. Only the player actually understands his or her fort's layout well enough to optimize pathfinding within it. Or optimize it for aesthetics so they'll actually use the nice paved roads, or if the player wants the manic little beard transports to be sure to wander past all the nice calming statuary.
I thought that was the point of traffic designations? How would you go about doing that without traffic designations?
Traffic designations only alter the costs of nearby cells, favouring A* pathing in certain directions.
Traffic designations only alter the costs of nearby cells, favouring A* pathing in certain directions.
The idea of manually setting control points is to have a pre-stored section of a path. So, you find the nearest control point, and calculate the nearest control point to your destination. If they're the same, you use normal path finding, if they're not you path to the first control point, follow the stored path to control point 2, and then path to the destination. It'd be best if you could manually link the control points into a network, then dwarves could sample the path from node to node to find the way to any destination very quickly.
Actually it might be better to be able define the search nodes on the scale of whole rooms (similar to burrow designations). Because with the "control point" system as i mentioned it above sometimes a dwarf would backtrack for no reason (since sometimes the destination square would be close to a node on the other side). Pathing into a region should alleviate that possible problem
Another option to storing whole paths is to store a series of waypoints sampling the path, then pathing from one waypoint to the next as you go - this could be used in the control point system eg storing portal/doorway locations between adjacent nodes
Partly incorrect. Traffic designations don't make A* favor pathing certain directions but through certain areas.
And the advantage of node points is better than traffic designations, as the idea is to give A* more shortcuts. Traffic areas reduce the number of processing cycles because A* checks fewer tiles. Pathing node points cause A* to get from one area to another without having to check ANY of the tiles in between.
Effectively, using node-points would cause there to be a wormhole in the map (as far as A* is concerned) with a "traffic cost" of 1/2/5 (depending on traffic settings of the end point) so that A* can skip across the fort with few itterations.
It doesn't need to make square rooms, it needs to make logical paths.
I'm pretty sure Toady already does this.
I just need to add easy maze load save like ?maze= with a hexadecimal or b64 value . Then after it's somewhat more functional I can start experimenting all sort of pathing methods ;) .
I'm might have mentioned it before but without a clear working algorithm like a computer program I doubt anything would come out of this thread.
I just did :D but the output is really long with hex but if you are well versed in binary you could almost see the maze ;) .I just need to add easy maze load save like ?maze= with a hexadecimal or b64 value . Then after it's somewhat more functional I can start experimenting all sort of pathing methods ;) .
You should do that.
I'll add a mode that outputs to that format to this little script I made yesterday that generates random maps (https://gist.github.com/876876).Python stuff ewww . I can probably convert that to JS - I can read pretty much any computer language ;). As I mentioned I like JS because it's easy to code in (for C coders) and runs on any web browser. I did notice that on mobile browser my page isn't working too well (not critical from my point of view but I might be able to fix it). I also added a code section generator to convert the maze into forum post-able (there is probably something like this in existence already that does the same thing).
I'm might have mentioned it before but without a clear working algorithm like a computer program I doubt anything would come out of this thread.True. I really need to study this stuff more.
Except that it only works for any given goal. It's also really CPU intensive as it ignores no tiles and every creature with a unique goal would need to build a weight-map.
I think the idea might be for every tile to store a map of the distance to every other tile from the beginning.
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.
Python stuff ewww .
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 ;).
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.)
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...
ah, nevermind, heavily ninjad.But you actually tested it (I just went off memory of past experiences), plus explained it far more succinctly.
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.
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.
I just did :D 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 ).
That wave front thing sounds like Breadth first search from the destination.
| 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 |
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!)
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.
-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 )
-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.
-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?
But if your rectangular prisms are just made of open space, you don't even need A* for internal navigation, you can just walk in a straight line.yep, that's the idea with a convex shape, we know the shortest path between every 2 points of the shape is the straight line, so there is no internal pathfinding to do.
And rebuilding a node is rather easy. I mean, if you stick a block in the middle of a big flat rectangle, you can just split it into two wide rectangles, and two narrow rectangles that fill the space that the original one did. No need for global rebuilding or anything like that. And removing the object would just work the other way around, generate a new tile, and see if you can merge it with a nearby rectangle (one edge is the same size as the adjoining rectangle), and repeat until you're done.
I wrote up a post on something like this (although without the funnel stuff, just A* from node to node) at http://www.bay12forums.com/smf/index.php?topic=42678
But if your rectangular prisms are just made of open space, you don't even need A* for internal navigation, you can just walk in a straight line.
012345_67
1# # |
|-----+---------
2# # |
3#####|##
4# # |
5
We are humans so we can see the rooms should be sliced between 3,4 while a computer without a proper algorithm can't "see" it( I'll give credit for my wife which was also a CS major). [...]since nodes only contain tiles that can be walk, flown, or swum to/in, things like constructions would obviously be excluded from them, as well as blocking tiles in workshops, locked doors, grates, etc.[...]Not really helping matters, here, but in a world where it is considered important to deal with the needs of all possible pathers[1], walk-through, fly-through and swim-through[2] tiles/nodes might need to be joined by dig-through and deconstruct-through. Which could end up with every single tile (leastwise all those that have been revealed to the agent[3]) having to be a member of at least one convex volume/node-map/whatever.
Do it like this:You could maybe apply the flag system to workshops too, that will prevent dwarves to pass through them, except those who have a job to do in it.
Find all walkable tiles, cluster into nodes (we'll treat workshops differently in a moment).
Then find all swim-able tiles, cluster into additional nodes with the "swim only" modifier (tiles that are in both, which I think is 3/7, are their own node).
(Do the same for magma).
Then find all remaining empty tiles, cluster into nodes, with the note "fly only."
Connect all neighboring nodes, the node connections will also carry the walk/fly/swim flags.
Done.
Now your volumes of sky are their own node, but dwarves can't path through it ("fly only").
Workshops we treat like this:
3x3* node centered on the workshop which splits the larger "room" node, which is then split thus:
1x1 node in the center as the destination (and walkable) (this aids pathfinding, as only the center tile is the workshop as far as item and locations).
Outside tiles are then removed if they are non-walkable, remaining are grouped as appropriate.
*For non-3x3 buildings, which exist, the node would be the building's size. The job-location node is split out as normal, followed by the subtraction of non-walkable spaces.
(BTW, one less complication that such extended thoughts about pathing brings about is that ghost-travel could ignore the tile status completely. Or, rather, be restricted to a historical layout, i.e. a path (or a small set of them) laid out at the time of 'deceasement', regardless of whether they now have to go through walls or other barriers, cross now unbridged chasms, haunt their way through flowing magma and running water with no impedance whatsoever.)
(BTW, one less complication that such extended thoughts about pathing brings about is that ghost-travel could ignore the tile status completely. Or, rather, be restricted to a historical layout, i.e. a path (or a small set of them) laid out at the time of 'deceasement', regardless of whether they now have to go through walls or other barriers, cross now unbridged chasms, haunt their way through flowing magma and running water with no impedance whatsoever.)
Ghosts have no reason to path to begin with. They can walk through everything, so you just do a straight line path. Or maybe you want them to pretend they were alive, in which case you can just cache a few paths just for them based on how things were when they died and have them wander the fortress in exactly the same way (even if it changes or someone builds a wall in the way). They are ghosts, after all. As far as they're concerned *all* tiles are walkable, so a straight line is always going to be the fastest way.
More or less what I meant. More or less in the order I said it. But I was probably too obtuse in the manner I did so. :)
Do it like this:
Find all walkable tiles, cluster into nodes (we'll treat workshops differently in a moment).
Then find all swim-able tiles, cluster into additional nodes with the "swim only" modifier (tiles that are in both, which I think is 3/7, are their own node).
(Do the same for magma).
Then find all remaining empty tiles, cluster into nodes, with the note "fly only."
Connect all neighboring nodes, the node connections will also carry the walk/fly/swim flags.
Done.
see my post here http://www.bay12forums.com/smf/index.php?topic=76278.msg2091518#msg2091518.Do it like this:
Find all walkable tiles, cluster into nodes (we'll treat workshops differently in a moment).
Then find all swim-able tiles, cluster into additional nodes with the "swim only" modifier (tiles that are in both, which I think is 3/7, are their own node).
(Do the same for magma).
Then find all remaining empty tiles, cluster into nodes, with the note "fly only."
Connect all neighboring nodes, the node connections will also carry the walk/fly/swim flags.
Done.
Here's something I've been thinking about, however - if you are drawing a map where you only make local updates, not global ones, odds are, you're going to start with a wide open field and some caverns and a functionally wide open HFS. You can basically start by just drawing a big grid over the land surface, and cutting up "rooms" every 12x12 set of tiles or something. Basically, everything starts out connected (excepting rivers or cliffs), so it should start out as a big grid with some unconnected grids down in the caverns. Obviously, you have to make separate rooms when you cannot path from one corner of these starting "rooms" to another, and may have to split things up if there are two different z-levels stacked over one another on the surface somehow or in caverns, but basically, it should look like a grid layed out over a varied set of slopes with some inaccessable tiles here and there because of trees or cavern walls.
Then, the instant you start digging into the earth, you basically start modifying or creating new rooms. If we go with doors creating their own nodes, and segregating rooms, we might have a situation where there is an entrance way, then the door nodes, then the hallway behind it, with all the little rooms or warehouses sprayed off of it.
If you just go by trying to make up 12x12x12 cubes, and looking for what paths are blocked (while having to make doors and drawbridges and floodgates and the like their own nodes, since they can be locked), then you'd wind up naturally adding bits and pieces into the simple starting map gradually. (Maybe, you'd need to have some sort of sanity check mop-up, maybe at the new year's, with all those other checks and calculations that make the whole thing take a long time processing, anyway, that another second checking to optimize the connection map wouldn't really be noticed.)
The map would probably wind up looking similar to Granite26's idea, with most of the inside-the-fort stuff being determined by doors and based upon z-levels, but it would have the capacity to react to having water or multi-z-level rooms (like if we eventually get proper flying unit pathing).
We just need to have a stored connectivity map that works in those area-nodes levels at that point, with an assumption we can A* to anything "local" within those nodes. Simply having a current location in the same node as a destination inherently implies not only connectivity, but a very short and probably direct pathfinding call. Then we can throw away the current version of the connectivity map, which makes the hierarchical nodal pathfinding structure capable of competing head-to-head with the current A* connectivity map in terms of memory - only the fact that you will need duplicate layers of connectivity maps for things like "flying only" or "water-based movement possible" or "swim only" really drags it down.
see my post here http://www.bay12forums.com/smf/index.php?topic=76278.msg2091518#msg2091518.
I would like that everyone stop posting their idea on how to do pathfinding cause THIS is the best method (see navigation mesh).
Instead try to point out:
-what we may have forget to take in consideration (like workshops or the need to represent all the tiles, even the unwalkable)
-how to easily implement one part of this method, or improving the current idea of implementation.(like using 3d shape instead of 2d, using a flag system for easily representing the different types of nodes)
This is only like this we'll have a serious suggestion that Toady may try to read.
I don't have a good english , so I would want that someone who understand the method post a summary each time someone post a potential improvement.
Here is the first summary:
-We represent the map with rectangular cuboid of tile of the same type (walkable/swimable/digable/flyable/magma/workshops)
-the map can now be represented as a graph where a node is a cuboid , and 2 nodes are connected if the cuboids they represent are touching.
-we use A* on this graph, this will give us a "basic" path, we'll know through what cuboid the path come, not what tiles.
-We have to use the funnel algorithm to knowing the exact path (http://digestingduck.blogspot.com/2010/03/simple-stupid-funnel-algorithm.html).
-At this point we have a set of points leading to destination , the dwarf only need to go in straight line between each points (There is no internal pathfinding, rectangular cuboid are CONVEX, the shortest path between 2 points is without any calculation the straight line)
-A straight line is defined as going diagonal (starting from starting point) until reaching one of the two coordonates of the destination then going horizontal or vertical.
-Each time a change is done on the map (digging, closing a door, building a wall etc...), we have to (slightly) change our graph.
-A function than can do this only need to be able to:
-add a node
-merge 2 nodes (if 2 cuboids have a common side)
-split a node (when we build a wall for example)
-changing the type of a node(digable->walkable)
With this method the entire map could be represented whith only few hundreds nodes instead of millions with the current method. And the more important thing, if we only look at the fortress (not the entire map), I think almost all pathfinding occur here, a friendly designed fortress could be represented with a dozen of nodes, and with only a depth of 4 nodes: the surface (surroundings by fortification) , the stairs , the main hall , all the other rooms linked to the main hall.
And finding a path in this type of graph is very fast.
In order for these nodes to work, you need to have any "local" pathfinding capable of finding the other tiles in the same node without leaving the node.
For someone who starts off by saying that he didn't read the thread, you're pretty quick to tell people not to post their thoughts on the subject because your ideas are the best. ::) What you've posted is basically a repeat of what others have said, except in a few cases that don't make much sense, like the funnel algorithm.
In case you didn't notice, I've been posting in this thread before, and was only talking about how the way in which this gets put into memory, because simply having fast pathfinding is NOT the only goal here - it also has to conserve memory and respond to dynamic changes extremely well. What you quoted wasn't a new idea, it was the same idea we've been talking about where I was disucssing how it could best fit those constraints on dynamic map changes.
(And to anyone else, what good ideas are there on ways to make a map react better to something like flooding with water as tiles individually flood or empty of water? For that matter, how do we handle things like digging or bridging in pathfinding cheaply?)
Anyway, just drawing cubes over the map is problematic as long as it is entirely possible for players to not have any vertical access between most areas of the map (such as the central stairwell method of fortress design). In order for these nodes to work, you need to have any "local" pathfinding capable of finding the other tiles in the same node without leaving the node. If you then have something like two or three minor hallways with rooms branched off of them, with no access through rooms to other hallways, you would need to make the one-tile tall functional square nodes smaller and skinnier, still, since you wouldn't be able to path from one hallway to another without first finding the major access hallways in other nodes.
I don't see any benefit to using funnel algorithm, which might make sense in a game with floating point location values, but seems like wasted cycles spent on "path smoothing" in a game that has no need for path smoothing. DF just needs to move diagonally when it can and horizontally when it can't. There are no other considerations that need to be taken into account.
The game already prefers diagonals, since they are functionally free (or rather, cost no more than a horizontal move), which means that point on preferring diagonals is pointless.
The changing of the node structure based upon locking doors or digging is exactly what I was talking about finding the best ways to accomidate in that last post. (You did read it, right?)
You also have to be aware of how the node changes aren't something as simple as "it's water now" - each individual tile will have to become flooded, and the game will likely be checking for which portions of the map are being flooded without a good system for how this will actually be updated.
Ok I read the whole thread , and like I thought it was mainly the same idea as the current pathfinding with some tweaks.
For what I can read of your post you didn't get almost every part of my method.
No there is no problem with fortress without vertical access.
No there is no need of any internal pathfinding , a cube is convex , which mean that for any two points of the cube the straight line conecting this two point is also include in the cube. Just in case a cube can be a 1x1x1 tile, which means this method is in the WORST case localy as fast(slow?) as the current method.
I think you just don't understand the funnel algorithm, it's an algorithm which take a bunch of touching convex polygons (with our start point in the first one and the end point in the last one), and returns you a bunch of straight lines conecting the 2 points, these straight lines ARE the path.
The function that take care of the changing of the map only do local changes not global, so it is very cheap in calculation.
I think the fluid system is as simple as "it's water now" (with an index of 1 to 7), I think the fluid system just need to know what is the "fluid index" of every tiles to work, but I may be wrong on this one.
Ho and the navigation mesh is known to be the (actual) best pathfinding method.
Edit: http://www.ai-blog.net/archives/000152.html here is a nice site explaining and showing some nice example of nav mesh.
A B C D
XXXXXXXX
B D F H
ABCDEFGH
Whether you call it a nav mesh or not, this is still functionally the same thing we have already been talking about, except for the fact that we are dealing with non-floating-point cubic tiles. You're coming into the thread, saying we should drop everything, and work on "your system", and then describe "your system" as being almost exactly what we were talking about (except that your is based upon floating-point distances), anyway, and then try telling us how much better your system is.there isn't any post (except the one of soralin in an other thread) relating to my method , but I don't care this is not MY method , this is just the most efficient method, I didn't invent it.
Also, no, it's not as simple as "it's water now". The entire node doesn't instantly fill with water. Only individual tiles fill with water, certain levels of water at a time, and do so sequentially - that means that at one point, there will be water in some of the tiles in one node, and not in other tiles in the node, and you are going to have to start splitting that node up and testing to see whether it fits in with other nearby nodes. There is an interface point (3/7 water) where swimming creatures and walking creatures can both occupy a tile. That means those tiles are probably going to be in their own individual nodes, and checking to be put in with other nearby nodes rather frequently, as water sloshes around randomly. In a situation with 3/7 and 4/7 water in a basin, the 4/7 water is going to be cutting off land access every time that 4/7 water depth shifts around, and that means the nodes are going to be cut up and merged very rapidly with one another. That's a potentially costly set of calculations to make, and something that can be optimized.You have a point here, even if you still don't understand a node represents a cube of tiles of the SAME type, that means there is only tiles with x/7 water in the same cube, so there is no problem for the walking thing, but it could be a lot of node rebuilding during a flood so maybe it could be improved. Though the complexities of the subroutines that add a node , merge 2 nodes , split one or change the type of a node are constant, so the complexity of the function will be linear to the amount of change (if there is 10 changes to do , it'll take as much time as doing 10 times 1 change), so I don't think it's a big deal.
Since I probably need to go into further detail as to why "Funnel" isn't helpful ...I think I need an example.
##################
#+++++#+X++#+++++#
#+++++#++++#+++++#
#+++++###+##+++++#
#++++++++++++++++#
#######++++#######
#+++++#++++#+++++#
#+++++#++++#+++++#
#++++++++++++++++#
#######++++#######
#+++++#++++#++Y++#
#+++++#++++#+++++#
#++++++++++++++++#
##################
this will be represented by something like that:##################
#22222#1X11#77777#
#22222#1111#77777#
#22222###a##77777#
#22222b6666c77777#
#######6666####### 1
#33333#6666#88888# |
#33333#6666#88888# 2-b a c-7
#33333g6666d88888# \|/
#######6666####### 3-g-6-d-8
#44444#6666#55Y55# / \
#44444#6666#55555# 4-f e-5
#44444f6666e55555#
##################
where 1,2,3,4,5,6,7,8,a,b,c,d,e,f,g are the nodes of the graph, X and Y the points we try to find a path for. X is in 1 , Y in 5.##################
#+++++#+X++#+++++#
#+++++#++++#+++++#
#+++++###A##+++++#
#++++++++++++++++#
#######++++#######
#+++++#++++#+++++#
#+++++#++++#+++++#
#++++++++++++++++#
#######++++#######
#+++++#++++#++Y++#
#+++++#++++#+++++#
#+++++++++BC+++++#
##################
Wich means go in straight line from X to A , then go in straight line from A to B , then go in straight line from B to C , then go in straight line from C to Y. You cant skip this step, knowing by wich cube you have to go through is not enough. This algorithm is extremly fast , and the A* has been through only 4-5 nodes instead of about 50 with the current method. I hope I've been clear and my post is understandable.However there are problems. The way the zones are created and coalesced has a huge effect on pathfinding.yes you are right, there is multiple possibilities to represent the same zone, and some are more optimized than other, I can't see right now a way to find out how to represent it optimaly, maybe if someone have an idea. But even a non optimized representation is at least as fast as considering each tile as a node, so it's totally worth it.
For example a corridor with cubby holes could be represented (at least) two ways. Letters represent pathfinding zones:Code: [Select]A B C D
XXXXXXXXCode: [Select]B D F H
ABCDEFGH
The second case is a bit of a disaster I think?
yes you are right, there is multiple possibilities to represent the same zone, and some are more optimized than other, I can't see right now a way to find out how to represent it optimaly, maybe if someone have an idea. But even a non optimized representation is at least as fast as considering each tile as a node, so it's totally worth it.
I don't care this is not MY method , this is just the most efficient method, I didn't invent it.
I don't know why you are talking about float, I never mention it. we use rectangular cube AxBxC where A,B,C are integers.
I think I need an example.
this will be represented by something like that:Code: [Select]##################where 1,2,3,4,5,6,7,8,a,b,c,d,e,f,g are the nodes of the graph, X and Y the points we try to find a path for. X is in 1 , Y in 5.
#22222#1X11#77777#
#22222#1111#77777#
#22222###a##77777#
#22222b6666c77777#
#######6666####### 1
#33333#6666#88888# |
#33333#6666#88888# 2-b a c-7
#33333g6666d88888# \|/
#######6666####### 3-g-6-d-8
#44444#6666#55Y55# / \
#44444#6666#55555# 4-f e-5
#44444f6666e55555#
##################
the A* will tell us , the path go through 1->a->6->e->5, but this is NOT the path, you have all the necessary information to easily find it , but you don't have it yet , you need the funnel algorithm (which is a very simple algorithm with integers mesh) to find out the exact path:Code: [Select]##################Wich means go in straight line from X to A , then go in straight line from A to B , then go in straight line from B to C , then go in straight line from C to Y. You cant skip this step, knowing by wich cube you have to go through is not enough. This algorithm is extremly fast , and the A* has been through only 4-5 nodes instead of about 50 with the current method. I hope I've been clear and my post is understandable.
#+++++#+X++#+++++#
#+++++#++++#+++++#
#+++++###A##+++++#
#++++++++++++++++#
#######++++#######
#+++++#++++#+++++#
#+++++#++++#+++++#
#++++++++++++++++#
#######++++#######
#+++++#++++#++Y++#
#+++++#++++#+++++#
#+++++++++BC+++++#
##################
As for water: it's easy. Any tile with water in it is its own node. You don't merge it with adjacent nodes until one of two conditions is reached:
1) Tile contains no water
2) Tile is marked as non-flowing
Dodging other walkers becomes easy if we only allow dodging to another square in the same segment. Yes this means there are times when dodging would help and we can't do it with the solution, but the pure simplicity of it will make it quick and under player control. five wide corridors will work still.
However there are problems. The way the zones are created and coalesced has a huge effect on pathfinding.
For example a corridor with cubby holes could be represented (at least) two ways. Letters represent pathfinding zones:Code: [Select]A B C D
XXXXXXXXCode: [Select]B D F H
ABCDEFGH
The second case is a bit of a disaster I think?
I apologise if I'm tearing this thread even more off subject, I've not read the whole thing as although I think it's hugely important to the game I really don't think I can solve the problem. And I get frustrated because I want the source code to generate traffic statistics and try optimisations on it myself :D
**You'd have to intentionally try and break it, as if you dig the corridor first, then the niches, you'll get the first solution. You'd have to dig 1 tile of corridor, then the nitch, then the neighboring tile and even then it'd depend on how the engine decided to do the merge. With my above rule, provided that our corridor is 2 tiles deep (as far as node-size is concerned) before digging a nitch, the nitch will never create a node that breaks the hallway into multiple nodes.
[Dug] [Meshed]
Start with a zig-zag
####### #######
#.#.#.# #b#d#f#
.#.#.#. a#c#e#g
####### #######
Then straighten the zig-zag
####### #######
#.#.#.# #b#d#f#
....... abcdefg
####### #######
You may want to save a little bit on digging by only half-cutting the corridor
####### #######
#.#.#.# #b#d#f#
#.#.#.# #b#d#f#
#.#.#.# #b#d#f#
.#.#.#. a#c#e#g
####### #######
Now the choice is between
####### #######
#b#d#f# #b#d#f#
#b#d#f# and #b#d#f#
#b#d#f# #b#d#f#
abc#e#g aaa#e#g
####### #######
aa#####
aa#####
##b####
###c###
####d##
#####ee
#####ee
aa#####
aa#####
##b####
###b###
####b##
#####ee
#####ee
bc#####
ab#####
##b####
###b###
####b##
#####be
#####db
######
###a##
##aa## Not possible (although all intra-'a' travel
#aaa## is still straight-line possible, even with
####b# that chunk taken out, so still convex)
#####?
######
###d##
##aa## One of the easy-splitting ways
#caa## (c.f. also the 1x1, 1x2 and 1x3 split)
####b#
#####?
######
###c##
##bc## Arguably more efficient,
#aab## although really depends on what use
####b# is made of the space.
#####?
Again, the problem I'm saying you seem to be having is that you're drawing distinctions between what I am talking about and what you are talking about that don't really exist. The difference between the sort of hierarchical node system and a nav mesh is largely nominal. It doesn't matter whether you call something a "node" or a "convex rectangular cuboid", so long as the code functions basically the same.well then sorry I may have misunderstood what your highway system is, and I'll reread your posts. (things like using limited 12x12x12 nodes, and "internal pathfinding" in your previous post may have induce me in error)
What I was talking about with a "highway" system would do exactly the same slicing of the map up into the same nodes, and follow basically the same path. The only real difference would be that the dwarf would hug the wall when walking through 6 until it came time to start moving diagonally to hit the door.
Nodes don't necessarily need to be rectanges every time - a "circular" node will make senseYeah, in theory any convex shape should do the job. (but may be difficult to represent)
A B C D
XXXXXXXX
B D F H
BBBBBBBB
Yes , the B shape IS convex with the definition of straight line I gave. A B C D
A B C D
XXXXXXXX
The main problem is how to come up with that node graph ;) .
this will be represented by something like that:Code: [Select]##################ng each tile as a node, so it's totally worth it.
#22222#1X11#77777#
#22222#1111#77777#
#22222###a##77777#
#22222b6666c77777#
#######6666####### 1
#33333#6666#88888# |
#33333#6666#88888# 2-b a c-7
#33333g6666d88888# \|/
#######6666####### 3-g-6-d-8
#44444#6666#55Y55# / \
#44444#6666#55555# 4-f e-5
#44444f6666e55555#
##################
Once we have the map sliced in rectangles, obtain the graph is trivial, slicing the map in rectangle is also trivial BUT slicing it optimaly is a much more difficult problem.The main problem is how to come up with that node graph ;) .
this will be represented by something like that:Code: [Select]##################
#22222#1X11#77777#
#22222#1111#77777#
#22222###a##77777#
#22222b6666c77777#
#######6666####### 1
#33333#6666#88888# |
#33333#6666#88888# 2-b a c-7
#33333g6666d88888# \|/
#######6666####### 3-g-6-d-8
#44444#6666#55Y55# / \
#44444#6666#55555# 4-f e-5
#44444f6666e55555#
##################
B D F H A-B-C-D-E-F-G-H is the graph representing it , the depth is 8
ABCDEFGH
A B C D
EEEEEEEEEEE
C
|
A-E-B is the graph , the depth is 3
|
D
So the 2nd representaion is better because the depth of the graph is smaller than the first one.##################
#+++++#+X++#+++++#
#+++++#++++#+++++#
#+++++###+##+++++#
#++++++++++++++++#
#######++++#######
#+++++#++++#+++++#
#+++++#++++#+++++#
#++++++++++++++++#
#######++++#######
#+++++#++++#++Y++#
#+++++#++++#+++++#
#++++++++++++++++#
##################
My idea consist to take all "maximal" rectangles, here are all of them################## ################## ##################
#AAAAA#GGGG#CCCCC# #+++++#++L+#+++++# #+++++#++++#+++++#
#AAAAA#GGGG#CCCCC# #+++++#++L+#+++++# #+++++#++++#+++++#
#AAAAA###+##CCCCC# #+++++###L##+++++# #+++++###+##+++++#
#AAAAA+FFFF+CCCCC# #++++++++L+++++++# #IIIIIIIIIIIIIIII#
#######FFFF####### #######++L+####### #######++++#######
#BBBBB#FFFF#DDDDD# #+++++#++L+#+++++# #+++++#++++#+++++#
#BBBBB#FFFF#DDDDD# #+++++#++L+#+++++# #+++++#++++#+++++#
#BBBBB+FFFF+DDDDD# #++++++++L+++++++# #JJJJJJJJJJJJJJJJ#
#######FFFF####### #######++L+####### #######++++#######
#HHHHH#FFFF#EEEEE# #+++++#++L+#+++++# #+++++#++++#+++++#
#HHHHH#FFFF#EEEEE# #+++++#++L+#+++++# #+++++#++++#+++++#
#HHHHH+FFFF+EEEEE# #++++++++L+++++++# #KKKKKKKKKKKKKKKK#
################## ################## ##################
the algorithm finding the "maximal" rectangles is very simple:
0)- just take a random tile
[...]
3)- look at all the tiles in this area that are touching a tile that is not in the area, take one of this tile
[...]
Once we have the map sliced in rectangles, obtain the graph is trivial, slicing the map in rectangle is also trivial BUT slicing it optimaly is a much more difficult problem.
The first question to ask is what is an optimal representation? I think it's a representation where the "depth" of the graph (the maximal distance (in nodes) between 2 nodes) is minimal
_0123456789abcdef
0##################
1#+#+++#++#+#+++#+#
2#+++#+#++++#+#+++#
3#+#+++###+##+++#+#
4#++++++#+++++#+++#
5#######++++#######
6#+#++##++#+#+++++#
7#++#++#++++#+++++#
8#+#+++++++#++++++#
9#######+#++#######
a#+++++#++#+#+#+++#
b#++#++#++++#+++#+#
c#++++#+++++++#+++#
d##################
Every step of this algorithm find a new maximal rectangle (The decomposition in maximal rectangle is unique) , so the starting tile doesn't matter, and I may be wrong but I think this algorithm is optimal. Here is an example step by step, the "X" are the choices we look at for the next step (the tiles in the area which are in contact with at least one tile wich is not in the area), the blank represent the area we've already cover. the A,B,C... are the maximal rectangles.the algorithm finding the "maximal" rectangles is very simple:
0)- just take a random tile
[...]
3)- look at all the tiles in this area that are touching a tile that is not in the area, take one of this tile
[...]
I'm not saying this is 'wrong', but I'm wary of aiming for optimality by starting off with a random tile, and continuing with random tiles.
Of all the possible starting/next tiles, there may be one that is the absolute worst-case (creating a very sub-optimal 'optimal' division and/ or leading down the route where the most work is put into the map compared with the savings it ends up giving).
################## ################## ##################
#+++++#++++#+++++# #+++++#++++#+++++# #+++++#++++#+++++#
#+++++#++++#+++++# #+++++#++++#+++++# #+++++#++++#+++++#
#+++++###+##+++++# #+++++###+##+++++# #+++++###+##+++++#
#++++++++++++++++# #++++++++++++++++# #++++++++++++++++#
#######++++####### #######++++####### #######++++#######
#+++++#++++#+X+++# #+++++#++++#AAAAA# #+++++#++++# # we choose randomly a X , there is only one.
#+++++#++++#+++++# #+++++#++++#AAAAA# #+++++#++++# #
#++++++++++++++++# #+++++++++++AAAAA# #+++++++++++X #
#######++++####### #######++++####### #######++++#######
#+++++#++++#+++++# #+++++#++++#+++++# #+++++#++++#+++++#
#+++++#++++#+++++# #+++++#++++#+++++# #+++++#++++#+++++#
#++++++++++++++++# #++++++++++++++++# #++++++++++++++++#
################## ################## ##################
################## ################## ##################
#+++++#++++#+++++# #+++++#++++#+++++# #+++++#++++#+++++#
#+++++#++++#+++++# #+++++#++++#+++++# #+++++#++++#+++++#
#+++++###+##+++++# #+++++###+##+++++# #+++++###+##+++++#
#++++++++++++++++# #++++++++++++++++# #++++++++++++++++#
#######++++####### #######++++####### #######++++####### we choose randomly a X , and call it Y
#+++++#++++# # #+++++#++++# # #+++++#++++#+++++#
#+++++#++++# # #+++++#++++# # #+++++#++++#+++++#
#BBBBBBBBBBBBBBBB# #XXXXX XXXX # #XXXXX XXYX #
#######++++####### #######++++####### #######++++#######
#+++++#++++#+++++# #+++++#++++#+++++# #+++++#++++#+++++#
#+++++#++++#+++++# #+++++#++++#+++++# #+++++#++++#+++++#
#++++++++++++++++# #++++++++++++++++# #++++++++++++++++#
################## ################## ##################
################## ##################
#+++++#++++#+++++# #+++++#++++#+++++#
#+++++#++++#+++++# #+++++#++++#+++++#
#+++++###+##+++++# #+++++###+##+++++#
#++++++CCCC++++++# #++++++X XX++++++#
#######CCCC####### ####### #######
#+++++#CCCC# # #+++++# # # we make the maximal rectangle from the previous Y, and starting again choosing randomly a X.
#+++++#CCCC# # #+++++# # #
#XXXXX CCCC # #XXXXX #
#######CCCC####### ####### #######
#+++++#CCCC#+++++# #+++++# #+++++#
#+++++#CCCC#+++++# #+++++# #+++++#
#++++++CCCC++++++# #++++++Y X++++++#
################## ##################
################## ##################
#+++++#++++#+++++# #+++++#++++#+++++#
#+++++#++++#+++++# #+++++#++++#+++++#
#+++++###+##+++++# #+++++###+##+++++#
#++++++X XX++++++# #++++++X YX++++++#
####### ####### ####### #######
#+++++# # # #+++++# # #
#+++++# # # #+++++# # #
#XXXXX # #XXXXX #
####### ####### ####### #######
#+++++# #+++++# #+++++# #+++++#
#+++++# #+++++# #+++++# #+++++#
#DDDDDDDDDDDDDDDD# #XXXXX XXXXX#
################## ##################
################## ##################
#+++++#++E+#+++++# #+++++#++X+#+++++#
#+++++#++E+#+++++# #+++++#++X+#+++++#
#+++++###E##+++++# #+++++### ##+++++#
#++++++X EX++++++# #++++++X X++++++#
####### E ####### ####### #######
#+++++# E # # #+++++# # #
#+++++# E # # #+++++# # #
#XXXXX E # #XYXXX #
####### E ####### ####### #######
#+++++# E #+++++# #+++++# #+++++#
#+++++# E #+++++# #+++++# #+++++#
#XXXXX E XXXXX# #XXXXX XXXXX#
################## ##################
################## ##################
#+++++#++X+#+++++# #+++++#++X+#+++++#
#+++++#++X+#+++++# #+++++#++X+#+++++#
#+++++### ##+++++# #+++++### ##+++++#
#++++++X X++++++# #++++++Y X++++++#
####### ####### ####### #######
#FFFFF# # # # # # #
#FFFFF# # # # # # #
#FFFFF # # #
####### ####### ####### #######
#+++++# #+++++# #+++++# #+++++#
#+++++# #+++++# #+++++# #+++++#
#XXXXX XXXXX# #XXXXX XXXXX#
################## ##################
################## ##################
#+++++#++X+#+++++# #+++++#++X+#+++++#
#+++++#++X+#+++++# #+++++#++Y+#+++++#
#+++++### ##+++++# #+++++### ##+++++#
#GGGGGGGGGGGGGGGG# #XXXXX XXXXX#
####### ####### ####### #######
# # # # # # # #
# # # # # # # #
# # # #
####### ####### ####### #######
#+++++# #+++++# #+++++# #+++++#
#+++++# #+++++# #+++++# #+++++#
#XXXXX XXXXX# #XXXXX XXXXX#
################## ##################
################## ##################
#+++++#HHHH#+++++# #+++++# #+++++#
#+++++#HHHH#+++++# #+++++# #+++++#
#+++++### ##+++++# #+++++### ##+++++#
#XXXXX XXXXX# #XXXXX XYXXX#
####### ####### ####### #######
# # # # # # # #
# # # # # # # #
# # # #
####### ####### ####### #######
#+++++# #+++++# #+++++# #+++++#
#+++++# #+++++# #+++++# #+++++#
#XXXXX XXXXX# #XXXXX XXXXX#
################## ##################
################## ##################
#+++++# #IIIII# #+++++# # #
#+++++# #IIIII# #+++++# # #
#+++++### ##IIIII# #+++++### ## #
#XXXXX IIIII# #XXXXX #
####### ####### ####### #######
# # # # # # # # the last steps are trivial
# # # # # # # #
# # # #
####### ####### ####### #######
#+++++# #+++++# #+++++# #+++++#
#+++++# #+++++# #+++++# #+++++#
#XXXXX XXXXX# #XXXXX XXXXX#
################## ##################
##################
Ω.Ω.Ω.Ω.Ω.Ω.Ω.Ω.Ω#
.................+
Ω...Ω...Ω...Ω...Ω#
.................+
Ω.Ω.Ω.Ω.Ω.Ω.Ω.Ω.Ω#
##################
##################
Ω.Ω.Ω...Ω...Ω.Ω.Ω#
......Ω...Ω......+
Ω...Ω...Ω...Ω...Ω#
......Ω...Ω......+
Ω.Ω.Ω...Ω...Ω.Ω.Ω#
##################
##################
Ω.Ω.Ω.<<Ω.<<Ω.Ω.Ω#
<<<<<<Ω.<<Ω.<<<<<+
Ω...Ω...Ω...Ω...Ω#
>>>>>.Ω>>.Ω>>>>>>+
Ω.Ω.Ω>>.Ω>>.Ω.Ω.Ω#
##################
Two things:
1) Please describe the Xs better. I had to read it four times and look at the image to figure out WTF it meant.
2) Why are you making maximum rectangles that overlap?
AAB
DCB
DEE
It is a possible repesentation of a rectangle that could be trivially represented as one node.##################
#s+++++++#d++++++#
#+##############+#
#++++++++#+#+#+#+#
#+########+#+#+#+#
#++++++++#+#+#+#+#
#+########+#+#+#+#
#++++++++#+#+#+#+#
#+########+#+#+#+#
#++++++++#+#+#+#+#
#+########+#+#+#+#
#++++++++++++++++#
#++++++++++++++++#
##################
##################
#sSSSSSSS#dDDDDDD#
#A##############J#
#AAAAAAAA#G#H#I#J#
#B########G#H#I#J#
#BBBBBBBB#G#H#I#J#
#C########G#H#I#J#
#CCCCCCCC#G#H#I#J#
#E########G#H#I#J#
#EEEEEEEE#G#H#I#J#
#E########G#H#I#J#
#FFFFFFFFFFFFFFFF#
#FFFFFFFFFFFFFFFF#
##################
G H I
\|/
S-A-B-C-E-F-J-D
As far as I've read and noticed A* is a variation of BFS (Breadth First search) where you prioritize the order in which you go through nodes by using the heuristic function. here is one of the worst cases:Do you have a method to be sure your map will be sliced like this and not like that:Code: [Select]##################
#sSSSSSSS#dDDDDDD#
#A##############J#
#AAAAAAAA#G#H#I#J#
#B########G#H#I#J#
#BBBBBBBB#G#H#I#J#
#C########G#H#I#J#
#CCCCCCCC#G#H#I#J#
#E########G#H#I#J#
#EEEEEEEE#G#H#I#J#
#E########G#H#I#J#
#FFFFFFFFFFFFFFFF#
#FFFFFFFFFFFFFFFF#
##################
As you can see it turns The pathing algorithm to simple path length 8 and then the sub-pathes between the nodes become a simple short paths which run in best case times .
So if you are asking if it's worth the trouble - it does . The advantages are huge compared to pure A*. While A* is a global algorithm (runs on the whole map) the node is a local algorithm which runs on a local area. Just think about 10X10 embarks with no performance degradation.
Giving fliers the option of vector Pathing through the air would also do a lot of good . Even though A* is optimal in air it's usually not necessary in air traversal which can use a vector (rise over run - like drawing lines ;) ) which is more or less O(1). If it hit the wall it would switch to A* and try to find it's "way in".
##################
#sSSSSSSS#dDDDDDD#
#Q##############J#
#AAAAAAAA#G#H#I#J#
#K########G#H#I#J#
#BBBBBBBB#G#H#I#J#
#L########G#H#I#J#
#CCCCCCCC#G#H#I#J#
#M########G#H#I#J#
#EEEEEEEE#G#H#I#J#
#N########G#H#I#J#
#FFFFFFFFFFFHOIPJ#
#FFFFFFFFFFFHOIPJ#
##################
Mohican:it's true, in the end it'll still be better. But we should start expliciting all the algorithms if we want that Toady give a look.
While sub-optimal, it's still fewer nodes (in the end that are saved) than the original A* path.
Something I'm not entirely sure we should overlook too soon, however, is ways to make some of these node non-rectangular. It might mean having to save some extra data into memory to ensure best paths or else involve some fairly quick A* work inside the node, but let me give an example...
Someone wants to build a really fancy hallway leading up to the dining room, with plenty of statues to impress visitors of the greatness of dwarven society...
(tricky) Case A:Code: [Select]##################
Ω.Ω.Ω.Ω.Ω.Ω.Ω.Ω.Ω#
.................+
Ω...Ω...Ω...Ω...Ω#
.................+
Ω.Ω.Ω.Ω.Ω.Ω.Ω.Ω.Ω#
##################
(sadistic) Case B:Code: [Select]##################
Ω.Ω.Ω...Ω...Ω.Ω.Ω#
......Ω...Ω......+
Ω...Ω...Ω...Ω...Ω#
......Ω...Ω......+
Ω.Ω.Ω...Ω...Ω.Ω.Ω#
##################
Now, in the case A, you can do a psuedo-optimization by just drawing some nodes horizontally, one tile wide, directly past the doors. You wouldn't be able to make it a wide hallway, but you could make the game recognize some hallways, at least. I'm not sure how well traffic dodging will work in this situation, however.
This requires a case of the game being able to actually make an optimal decision on how to cut up these nodes, however, in order to get optimal results.
The case B, however, will inherently screw any attempt at making an orderly straight line through the hallway over. You're going to have to make the pathfinding program find a way to dodge occasional obstacles in otherwise straight hallways.
Now, what I'm wondering if we could try to do is make slightly more permissive definitions of nodes than just drawing rectangles, and then going ahead and either recording an optimal path through the hallway (costs memory), or else just letting a "local A*" type of pathfinding take place (costs more processor power at the time pathfinding takes place), but at the same time, making a much simpler node graph (saving some memory and time spent searching paths through the nodes), but also taking some more complex node-generation techniques (taking more processor time when building the graph itself).
Hallway case A, for example, could have one node taking up all three middle rows of tiles (not including the alcoves), and record that there are some obstacles in some of those middle tiles, and the whole hallway would just be a single node, and dwarves could path up and down diagonally through that hallway if they so chose, weaving in and out of those statues if there was an obstruction like a traffic congestion down by one of the statues, and they had to go around to save time.
Hallway case A might even fill to include the whole darn hallway, alcoves and all, and just have plenty of obstructions out along the sides as well as in the middle to avoid.
Either way, you could have some sort of very basic A* pathfinding that would work very, very well, or else have a pre-saved optimal path from one exit of the hallway to another that ties up memory.
Hallway case B might have the entire hallway stored as a single node, once again, with an optimal path to and from exits based upon the sort of highway system, to avoid traffic collisions:
("<" means the "going left" path and ">" means the "going right" path)Code: [Select]##################
Ω.Ω.Ω.<<Ω.<<Ω.Ω.Ω#
<<<<<<Ω.<<Ω.<<<<<+
Ω...Ω...Ω...Ω...Ω#
>>>>>.Ω>>.Ω>>>>>>+
Ω.Ω.Ω>>.Ω>>.Ω.Ω.Ω#
##################
Um, guys?... Any response on this?Spoiler (click to show/hide)
..........
.......Ω..
....Ω.Ω...
.....Ω....
..Ω..Ω....
..........
....Ω.....
..........
...Ω..Ω...
..........
..Ω.......
..Ω.......
..Ω.......
..Ω.......
..Ω.......
..Ω.......
..Ω.......
..Ω.......
..Ω.......
..Ω.......
############
#..#.#.#.#.#
#..........#
#.##########
#..........#
##########.#
#..........#
##########.#
#..........#
##########.#
#..........#
############
############
#aa#a#b#b#d#
#aaaabbbbbb#
#a##########
#ccccccccee#
##########e#
#fffffffeee#
##########e#
#igggggggge#
##########h#
#jjjhhhhhhh#
############
############
#aa#a#b#b#b#
#aaaabbbbbb#
#a##########
#ccccccccee#
##########e#
#fffffffeee#
##########e#
#ggggggggge#
##########h#
#hhhhhhhhhh#
############
Um, guys?... Any response on this?Spoiler (click to show/hide)
##################
#.#.#.#.#.#.#.#.##
##.#.#.#.#.#.#.#.#
#.#.#.#.#.#.#.#.##
##.#.#.#.#.#.#.#.#
#.#.#.#.#.#.#.#.##
##.#.#.#.#.#.#.#.#
#.#.#.#.#.#.#.#.##
##.#.#.#.#.#.#.#.#
#.#.#.#.#.#.#.#.##
##.#.#.#.#.#.#.#.#
#.#.#.#.#.#.#.#.##
##.#.#.#.#.#.#.#.#
#.#.#.#.#.#.#.#.##
##.#.#.#.#.#.#.#.#
#.#.#.#.#.#.#.#.##
##.#.#.#.#.#.#.#.#
##################
##################
################.#
###############..#
##############...#
#############....#
############.....#
###########......#
##########.......#
#########........#
########.........#
#######..........#
######...........#
#####............#
####.............#
###..............#
##...............#
##################
If we're doing convex polygons, then your diagonal hallway there IS a convex polygon, therefore can be one node.Some forms of this discussion have been dealing with convex (i.e. all of them) rectangles, though. Easier to work out (the simple way is, from a spot, expand N-S and E-W by varying amounts until you have the largest area you like the look of, either by total area or sum of each axis length), easier to define (TLx,TLy,BRx,BRy), easier to check to see whether a random tile is within its bounds or not ( <= compare with previously stated limits), etc.
#######
##1..2#
##....#
#....##
##...##
##..###
##..###
##3####
#######Even that single open space to the left is 'within' the triangle defined by the points 1, 2 and 3, and the RHS could easily be either straight down from 3, before exact diagonal to 3, or diagonally in before straight down, at the extreme limits of possibilities for that line.
I don't think anyone really gets your 'highway' concept (though I do think it would be useful). How exactly is the computer supposed to figure out where those traffic patterns go, anyway?
For comparison, worst-case for unaided A* is a wide, contiguous up/down stair column, so YMMV.
##################
#s+++++++#d++++++#
#+##############+#
#++++++++#+#+#+#+#
#+########+#+#+#+#
#++++++++#+#+#+#+#
#+########+#+#+#+#
#++++++++#+#+#+#+#
#+########+#+#+#+#
#++++++++#+#+#+#+#
#+########+#+#+#+#
#++++++++++++++++#
#++++++++++++++++#
##################Regarding those hell maps, they are still better than unaided A*. The worst case scenario for the convex polygon method is still half as intensive as unaided A* (it does gain that at the cost of greater memory overhead), and looks like this:Code: [Select]##################
#.#.#.#.#.#.#.#.##
##.#.#.#.#.#.#.#.#
#.#.#.#.#.#.#.#.##
##.#.#.#.#.#.#.#.#
#.#.#.#.#.#.#.#.##
##.#.#.#.#.#.#.#.#
#.#.#.#.#.#.#.#.##
##.#.#.#.#.#.#.#.#
#.#.#.#.#.#.#.#.##
##.#.#.#.#.#.#.#.#
#.#.#.#.#.#.#.#.##
##.#.#.#.#.#.#.#.#
#.#.#.#.#.#.#.#.##
##.#.#.#.#.#.#.#.#
#.#.#.#.#.#.#.#.##
##.#.#.#.#.#.#.#.#
##################
Also, I have a diagonal version of the notched corridor that I'm puzzling over. Ideal packing is one large node in the bottom corner, and successively smaller nodes adjacent to it, with 1x1 nodes only between larger nodes (think Sierpinski triangle). I don't know how to get that, though. On the other hand, I don't think ideal packing is ideal for pathing (at least via the funnel algorithm), so it may not matter.Code: [Select]##################
################.#
###############..#
##############...#
#############....#
############.....#
###########......#
##########.......#
#########........#
########.........#
#######..........#
######...........#
#####............#
####.............#
###..............#
##...............#
##################
And kaenneth, try to keep convex nodes, otherwise intra-node navigation needs A* to work.
Or you could limit it to only 45 degree angle lines. That would get you some non-grid convex shapes without having to go into complex math.
I don't think anyone really gets your 'highway' concept (though I do think it would be useful). How exactly is the computer supposed to figure out where those traffic patterns go, anyway?
The game has to store a "path width" (which would be necessary for vehicles, anyway) for the nodes, and prefer to travel down the far right side. If you have a three-tile-wide rectangular hallway, the dwarves would prefer to stay on the right hand side of that hallway, given their current direction of movement, hence making opposing traffic stay on either side of the hallway, the way that cars stay on the right (or left in certain countries) when driving down a road to prevent traffic collisions.
Yes, A* uses up cycle time, but if we make a map that has 80,000 nodes in it because we have so many one-tile nodes, you're probably going to need to use A* or something to even navigate the node map in the first place, completely nullifying the point of the whole operation.
Should we divide this room up into four separate nodes? Or should it just be one big node where we give the dwarves the ability to path around the obstacle if they happen to go towards it?
Again, the problem with A* is not finding its way through mostly open areas, it's preventing A* from going down dead ends. If you just find the dead ends and mark them off, A* works perfectly well. That's all the hierarchical/nodal structure needs to do - zoom out to an abstract model, and find the zones that are the "leaf nodes" that are dead ends, the "branch nodes" that provide access to some local areas, and the "trunk nodes" that are the main throughfares that serve as the access points to all the other portions of the fortress.
Now, the complexity of the system that divides up the rooms is a major sticking point - it needs to be fast enough that the computer doesn't spend more time dicking around looking for a "perfect" set of nodes than it does pathfinding in the first place, and it also needs to conserve on memory as much as it can, but these are all tradeoffs that should be balanced, rather than going for maximizing any one to the exclusion of all others.
I don't think anyone really gets your 'highway' concept (though I do think it would be useful). How exactly is the computer supposed to figure out where those traffic patterns go, anyway?
The game has to store a "path width" (which would be necessary for vehicles, anyway) for the nodes, and prefer to travel down the far right side. If you have a three-tile-wide rectangular hallway, the dwarves would prefer to stay on the right hand side of that hallway, given their current direction of movement, hence making opposing traffic stay on either side of the hallway, the way that cars stay on the right (or left in certain countries) when driving down a road to prevent traffic collisions.
I'm not convinced. How does it know the difference between a corridor and a dinning room? If you want to move north s few squares in a room and you're on the wrong side do you run to the other side first? It seems more like this is overcomplicating the path finding algorithm for a feature that should be handled at a higher level.
I'm not convinced. How does it know the difference between a corridor and a dinning room? If you want to move north s few squares in a room and you're on the wrong side do you run to the other side first? It seems more like this is overcomplicating the path finding algorithm for a feature that should be handled at a higher level.
Also as a player this would drive me mad unless I have control over it. With normal zones (whether rectangular, convex, or otherwise) we can allow the player to paint one way signs and attach the zone to the node graph with acyclic links. I think this would be a better solution, if we do need one.
Also, using convex zones solves the path width problem quite nicely too.
QuoteAgain, the problem with A* is not finding its way through mostly open areas, it's preventing A* from going down dead ends. If you just find the dead ends and mark them off, A* works perfectly well. That's all the hierarchical/nodal structure needs to do - zoom out to an abstract model, and find the zones that are the "leaf nodes" that are dead ends, the "branch nodes" that provide access to some local areas, and the "trunk nodes" that are the main throughfares that serve as the access points to all the other portions of the fortress.
We can just add another level of heirarchy? Using the simplest possible representation at the lowest level and having multiple self-similar levels of abstraction on top is usually a pretty good algorithm.
And simple enough to code it quickly with no bugs.
There is no such thing as code that you can make quickly without bugs.
[...]the thing about A* is that you can always tell if you are moving "closer" or "further away" from your destination when you are moving, thanks to the heuristic. In an abstract node map, it's much more difficult to make that sort of heuristic take the guesswork out of whether you are moving closer to the target or not without actually looking at all of the nodes - which again, is a major problem when you have potentially thousands of nodes.
I know I'm not really addressing this issue head-on, and this method includes an overhead which makes the smallest-extending nodes far less efficient (but should be ok for the largest ones, at least), but if the centre-spot[1] coordinates are recorded for each node then it gives a basis towards a "that adjacent node looks closer than this other adjacent node, and this other one looks to be a back-tracking one (but we may still have to come back to it later)" analysis along the lines of the standard A* tile-by-tile heuristic.
(From a personal POV, I'm most concerned about the node-weightings situation. A zone with five different entrances to it may be made into a node in a search-map net, but has to remember up to 10 different 'costs' in order to convey to the route-finding algorithm how much effort it takes to get so-many X, so-many Y and so-many Z[2] nearer the target. And that's with single-width entrances. I'm still hung-up on a series of multi-width connections between a string of zones, where twists and turns dictate that there are better and worse paths across a zone purely due to where the zones on either side have their entrances and exits to the zones once-more-removed, or even beyond. Sorry, please ignore this complication in my own fiddling with my own code, which isn't exactly keeping pace or mirroring the heading of everything else being discussed here, so this whole issue is probably not worth talking about.)
[1] Need not involve integer values, for X, Y or Z... and could be mid-way between the respective limits or a true average of all contained co-ordinates.
[2] Any or all of which may be zero or even negative values.
You can do that, but the thing is, we generally want to try to at least keep in mind which nodes are the dead end nodes.[...]I know, I was just addressing the "A* has an idea of what may be closer" idea. Which wasn't quite what you were talking about, as I tried to acknowledge.
I'm not sure I understand your last two sentences in your second paragraph, though.Well, the very last sentence was telling you to ignore the ramblings from the previous four sentences in that para.
####### #######
#+++++# #+++++#
#+++++# #+++++#
#++A++# #++B++#
#+++++# #+++++#
#+++++# 2#+++++#
##+++#########+++##
#+++++#1+++2#+++++#
#+++++++++++++++++#
#++C+++++++++++D++#
#+++++++++++++++++#
#+++++#3+++4#+++++#
##+++#########+++##
#+++++# #+++++#
#+++++# #+++++#
#++E++# #++F++#
#+++++# #+++++#
#+++++# #+++++#
####### #######
Assuming that A..G represents zone names for shapes that inhabit something roughly equivalent to the whole 5x5 room they're ensconced in (and the 1x3 gaps joining them are either part of convex shapes A..G or their own individual but un-named connecting rectangles... or possibly shared-tiles belonging to both zones as part of the connectivity matrix), and that travel from X->Y means anywhere-in-X-zone to anwhere-in-Y-zone... (By convention, letters from the top-end of the alphabet will be arbitrary designations. There's already no particularly logical order of letters even in the bottom-end set, which will latter extend to encompass A..J anyway, but they at least relate to the features you can see or imagine being added on.)OK, it's getting kind of late for me, so my mind is getting a bit fuzzy, and you kind of lose me near the end where you start talking about X and Y and Z but not really Y and Z, but V and W. (Or where on the map H-I-J is.)1) Don't worry about it, I was just trying to explain (badly, it seems) the issue I had made an off-hand comment about.
A B
CGD
E F
HIJ
The idea being that E->F travel might have been 'tempted' to go via HIJ instead of CGD, depending on where in E and F the end-points were. (The labels were for zones only, not specific end-points within those rooms.)Number of nodes per level:
Level 2^ 5^ 10^
0 1 1 1
1 2 5 10
2 4 25 100
3 8 125 1000
4 16 625 936
5 32 1266
6 64
7 128
8 256
9 512
10 1024
Top-Down memory Allocation:
Level 2^ 5^ 10^
0 2046 2046 2046
1 2044 2041 2036
2 2040 2016 1936
3 2032 1891 936
4 2016 1266 0
5 1984 0
6 1920
7 1792
8 1536
9 1024
10 0
Bottom-Up Memory Allocation:
Level 2^ 5^ 10^
0 0 0 0
1 2 5 10
2 8 50 200
3 24 375 3000
4 64 2500 3744
5 160 6330
6 384
7 896
8 2048
9 4608
10 10240
Sums:
Bottom-up:
2^ 5^ 10^
18434 9260 6954
Top-Down:
2^ 5^ 10^
18434 9260 6954
Nodes don't need to be rectangles.
They can be rectangles, but don't need to be...
You can have convex shapes, like the right triangle shape, and it breaks no assumptions.
You can also have non-rectangular shapes like a circular shape.
Now, you can make that entire circular room a node. Depending on what sort of pathfinding you use, you can make the whole outer circle around that room be a big node, as well. All the tiles in the node are accessable, you just need a small amount of A* pathfinding to find a route around the circular room's walls. So long as A* is bounded into a "local node pathfinding" where the shapes are guaranteed to be simple, you can still use A* very efficiently.
After that, you don't need to have overlapping rooms.
\/room A room B\/
##################
######++#++++++++#
####++++#++++++++#
###+++++#++++++++#
##+++++++++++++++#
##++++++#++++++++#
#+++++++#++++++++#
#+++++++#++++++++#
#+++++++#++++++++#
##################
as you see room A has an arc in top left corner this means. The "link" generated by the my program has a bit vector with a 1 where there is a wall so if we want to exclude the walls we just need to invert it.F900
E100
C100
8000
8100
0100
0100
0100
FFFF
Room A mask is done by removing room B and inverting bits of A ( I included the entrance to B in room A)hex | binarry
0600 | 00000110 00000000
1E00 | 00011110 00000000
3E00 | 00111110 00000000
7E00 | 01111110 00000000
7F00 | 01111111 00000000
FE00 | 11111110 00000000
FE00 | 11111110 00000000
FE00 | 11111110 00000000
0000 | 00000000 00000000
Oh, and making a coordinate into a node id is fairly easy - just take the x-coordinate, make it the first eight bits (768 tiles are the maximum number of tiles horizontally), take the y-coordinate, make it the second 8 bits, and then make the z-coordinate the rest of the bits.
You could also do it hash-style, but this would probably be faster and cleaner.
Well we gotta start with something. My idea was based on using A* pathing algorithm or D* lite ( start at destination find the source).
Anyways about room shape If we make maximum room size 16X16 we can save a bit vector (more of a bit map) of the shape of the room with 32 bytes . My little test_maze page uses that format to "save " mazes . With a "bit vector" we can save any arbitrary shaped room in a very compact manner which can easily tell weather a node is in a room or not.
this is how it works:Code: [Select]\/room A room B\/as you see room A has an arc in top left corner this means. The "link" generated by the my program has a bit vector with a 1 where there is a wall so if we want to exclude the walls we just need to invert it.
##################
######++#++++++++#
####++++#++++++++#
###+++++#++++++++#
##+++++++++++++++#
##++++++#++++++++#
#+++++++#++++++++#
#+++++++#++++++++#
#+++++++#++++++++#
##################
The map representation in hex is (the borders are excluded):Code: [Select]F900Room A mask is done by removing room B and inverting bits of A ( I included the entrance to B in room A)
E100
C100
8000
8100
0100
0100
0100
FFFFCode: [Select]hex | binarry
0600 | 00000110 00000000
1E00 | 00011110 00000000
3E00 | 00111110 00000000
7E00 | 01111110 00000000
7F00 | 01111111 00000000
FE00 | 11111110 00000000
FE00 | 11111110 00000000
FE00 | 11111110 00000000
0000 | 00000000 00000000
This way rooms can be saved in rectangles regardless of their shape and overlaps will not happen. You can make this bitmap variable length but keeping it constant may help with cache performance.
Using 4x4 embark X200 levels that would be the bitmap would use about 1MB of space. Converting a BFS and trading node would be fairly trivial in this case. It would take some bit manipulation but those actions are super fast .
I'm sorry, I'm not sure I'm catching something, here...
What happens if the 16x16 block you cut up into rooms involves rooms that do not touch each other, and which touch entirely different nodes, here?
_01234567
0#######
1#+#+++#
2#+###+#
3#+++#+#
4#+###+#
5#+#+++#
6#+###+#
7#+++++#
8#######
100
100
111
100
100
100
111
111
001
001
001
111
001
001
011
Also, this whole plan seems to have nothing for vertical pathfinding - how will fliers and swimmers be able to pathfind using this?
You did it wrong again.
The question was for a layout like this:
_01234567
0#######
1#+#+++#
2#+###+#
3#+++#+#
4#+###+#
5#+#+++#
6#+###+#
7#+++#+#
8#######
If you have a room in the north end of a 16x16 block that accesses the north side of that node, then have a room in the south end that only has access to other nodes on the south end, and store that as "this 16x16 block has access from the south and the north", but there is no connection from the north to the south, then you would be falsely storing a notion that if you can access the north and the south from that node, that you could path from the south to the north through that node.
In other words, like this:
_01234567
0###+###
1#+#+++#
2#+###+#
3#+++#+#
4#+###+#
5#+#+++#
6#+###+#
7#+++#+#
8###+###
Where there are other nodes to the north and south.
##################
#A#AAAAAAAAAAAAAA#
#A#A############A#
#A#BBBBBBBBBBBB#A#
#A#BBBBBBBBBBBB#A#
#A#BB######BBBB#A#
#A#BB#CCCC#BBBB#A#
#A#BX#CCXC#BBBB#A#
#A#BX#CCXC#BBBB#A#
#A#BX#CCXC#BBBB#A#
#A#BB######BBBB#A#
#A#BBBBBBBBBBBB#A#
#A#BBBBBBBBBBBB#A#
#A#BBBBBBBBBBBB#A#
#A#BBBBBBBBBBBB#A#
#A##############A#
#AAAAAAAAAAAAAAAA#
##################
typedef struct
{
int id;
int x1,y1,x2,y2; /* height and width are derived values */
unsigned int cost;
char * nodeBitVector /* could be other data type to store this data */
iint numEdges;/* can use smaller data type to */
int * edgeList /* can either be constant or dynamically growing base type this can also be a complex type */
}
tNode;
E F G
\|/
H-A-B-C-D
|
I
EFG###
HABCD
#I####
# is empty node.
edge list :
E = SE
F= S
G= SW
H= E
A = W NW N NE E S
B= E W
etc
If we are dealing with nodes, an almost arbitrarily large number of nodes can spring off of a node. (Imagine a hallway with small bedrooms coming off of them, divided by doors which would preferably be their own node so that they can be locked and made disconnected.) With up to 16x16 tiles, that's up to 8 bedrooms per side. Plus stairs coming in and out.16X16 was picked arbitrarily in general it's a 256bit vector of 32bytes. It gave me a ballpark figure on how much memory it would consume. in my struct it uses it as a dynamically allocated vector but the implementation is all defendant on the programmer. In a 256 bit vector you can store any rectangle that contains 256 nodes. This vector can represent a room within a 16X16 square ,a 8X32 rectangle or a 4X64 hallway .
About the data type that stores node connectivity - where is that stored, separate from the nodes themselves? (I.E. Do the nodes themselves store what they are connected to?)That's an option but it's not very desireable as it would make the memory use grow by about 1.8MB per embark square or 461KB if you use a byte and a z level lookup table. Even if you go through a linear search and just keep a lookup table for each z you'll find your start point fairly fast. It's like 9 nodes per embark square or 144 per 4X4 embark .
And how do you traverse it? For that node A, I would expect you would have to store at least one instance of pathing data per permutation of connections through A connecting to any of the nodes A is adjacent to. (Plus you might need multiple types for different travel methods - fliers and swimmers and large vehicles would take different types of connections.)I'm suggesting a pointer or pointer like connected graph with Inner traversal of A*. First the dwarf would find the path on the upper level graph and then it would step through that graph by creating subpaths with A* . As I said (x+1)*K^W instead of K^(W*x). Flyers should also have more advance pathing like vector pathing which is much faster runtime to find a good starting point for A* .
Does toady even read this thread?I think it's more a matter of demonstrating an alternative and not a matter of reading ;).
I always thought caching commonly used paths would be helpful. ie: caching the path between workshops and stockpiles.I'm not sure anyone have demonstrated that yet many people talk about it but none gave a practical implementation. the paths are dynamically generated and there are just too many possibilities . There was the idea of highways but it would again mean generating an overlaying map.
I imagine with only a few megabytes of cache, quite a few paths could be cached, reducing the load on the cpu.
S_A_B
##X#X
##X#X
##X#X
##X#X
##X#X
##C#D
#####
Considering this and storing paths by moves N,S,E,W,U,D gives 26 posibilities and if you remove the vertical diagonals it's 10. Using 4 bits to represent you can do 200 step path in 100 bytes .
Considering this and storing paths by moves N,S,E,W,U,D gives 26 posibilities and if you remove the vertical diagonals it's 10. Using 4 bits to represent you can do 200 step path in 100 bytes .
Well, that gets back to the problem I was talking about before about how nodes make connections -
The problem is, you can't store nodes as strict "N, NW, E, SE, S, SW, W, NW, U, D" types of connections - you need a virtually arbitrary number of connections to any given node.
Especially if you are going to make it possible for a 2x128 hallway to be a single node, there could be potentially over a hundred different nodes sticking off of that one hallway node in the form of stairs going up and down and different narrow rooms that are their own nodes sticking off that hallway.
##################
#+++++#++++#+++++#
#++A++#++B+#++C++#
#+++++###+##+++++#
#++D+++++E++++F++#
#######++++#######
#+++++#++++#+++++#
#++G++#++H+#++I++#
#++++++++++++++++#
#######++++#######
#+++++#++++#+++++#
#++K++#+J++#+++L+#
#++++++++++++++++#
##################
room division B C
| |
A-D-E-F-C
|
G-H-I
|
K-J-L
A-B 2SE,3E,1NE,N,stop
A-C 2SE,7E,2NE,E,stop
A-D 2S,stop
.
.
You're still not getting it.
How would it work in this situation?
#########
#..#.#..#
#.......#
#..#.#..#
####.####
#..#.#..#
#.......#
#..#.#..#
####.####
#..#.#..#
#.......#
#..#.#..#
####.####
#..#.#..#
#.......#
#..#.#..#
####.####
You're still not getting it.
How would it work in this situation?
#########
#..#.#..#
#.......#
#..#.#..#
####.####
#..#.#..#
#.......#
#..#.#..#
####.####
#..#.#..#
#.......#
#..#.#..#
####.####
#..#.#..#
#.......#
#..#.#..#
####.####
which method and what constraints?
Path caching require some start point and end point selection and a node placement scheme. Maze solving isn't the point it's teaching the computer to do it.
I can probably write a JS path caching demo pretty quickly . I got a 5 hour bus drive tomorrow (going to Eilat ) so I can probably even do a room method demo.
What a path caching scheme would do is simply place nodes in different spots, find the path from each node and save it and then use the saved paths to reach the destination.
a room divider would pick somekind of constraint on room size and start slicing the map arbitrarily , do room validations and split them when needed . after that map neighboring rooms . Then it might go through a room merge stage if needed. Pathing would be done by deciding which room you are in, finding a path on the map and then take that path using A* as subpath.
Path caching would take some validation too and if the path you are given tell you to go through a wall you'll have to recalculate it. I also think my estimate was bad because the pathes are 2 way so the paths in the cache can be stored in half the memory.
OK, let's do it like this...
#########
#..#.#..#
#.......#
#..#.#..#
####.####
#..#.#..#
#.......#
#..#.#..#
####.####
#..#.#..#
#.......#
#..#.#..#
####.####
#..#.#..#
#.......#
#..#.#..#
####.####
Let's call the middle hallway "A". Let's then call each room "B" through "I", and connecting to some other node "J" to the south. The middle hallway would be a very long "A" node, with the following forks:
B\ /C
D-A-E
F/ \G
H/|\I
J
Now, we have 9 horizontal connections to "A" in a method that only allows for 8 horizontal connections - in this case, two different nodes are "southwest" and two different nodes are "southeast" of "A".
which method and what constraints?
...I had the same idea and searched in this and other threads for it, but nobody gave feedback to it afaik.
Question: Has Toady ever mentioned taking the principle of stigmergy from the ACO scheme in order to dynamically modify the PATH_COST value for tiles as dwarves travel over those tiles? My thought is that since we can already improve framerate by manually designating High Traffic Areas, perhaps inserting some code to dynamically modify High Traffic areas as the dwarves are travelling would provide the same benefit while keeping the same A* algorithm in place.
...
What about the thing this guy said?...I had the same idea and searched in this and other threads for it, but nobody gave feedback to it afaik.
Question: Has Toady ever mentioned taking the principle of stigmergy from the ACO scheme in order to dynamically modify the PATH_COST value for tiles as dwarves travel over those tiles? My thought is that since we can already improve framerate by manually designating High Traffic Areas, perhaps inserting some code to dynamically modify High Traffic areas as the dwarves are travelling would provide the same benefit while keeping the same A* algorithm in place.
...
Wouldnt this work?
Just add a value for every tile that increases every time a dwarf walks over a tikle and globally decrease it periodically. The search algorithm would priorize high traffic tiles over others.
Sorry if its dumb...too obvious or whatever I'm just curious.
If you work with nodes, you could possibly start working with a "commonly used node" idea. Either a "I'm specifically going from this node to this node" type of concept, where you would have to store the start and end points, although this is typically memory-wasteful, or by just weighting the node every time it is used.
I was talking earlier about weighting nodes - by using a counter where you bias a node so that the computer is more likely to search for a connection using a given node before any other if they have a high bias in their counter, and adding to that bias each time the connection does turn out to path through the node, and then subtracting from that bias counter every time you cannot path through that node to the destination, you will wind up with "major artery" types of nodes (like major hallways) rising up high in their bias counters, and paths that only lead to dead ends winding up with negative scores.
Doing that sort of thing can help you rebalance what nodes you try to path through in some methods of pathfinding.
The problem with stigmergy in general is that it is potentially very memory-consuming, and doesn't necessarily improve pathfinding speed terribly much if you're just putting it on standard A*, anyway, at least until you have a bias hundreds or thousands of points strong so that dead ends are almost never pathed down. In order to do that, you'd need something like 16 bits of data per tile, which is potentially a large amount of memory.
I can do both ;)which method and what constraints?
Your most recent example.
Just to point out:You know, it's pathetically easy to write code that can flood-fill and detect rectangular areas? Bigger size rooms will make any node or room-based search algorithm far more efficient than pure A*. It's the small rooms / close packed where you would see less % improvement.
You've always been choosing a room division size in order to convenience yourself. You're not allowed to chose the "best case scenario" for each example.
For example, what if the first step returned this?
[...]
What it the rooms were larger (rather than the quick and dirty 2x3 rooms I made)?
[...]
Just to point out:You know, it's pathetically easy to write code that can flood-fill and detect rectangular areas? Bigger size rooms will make any node or room-based search algorithm far more efficient than pure A*. It's the small rooms / close packed where you would see less % improvement.
You've always been choosing a room division size in order to convenience yourself. You're not allowed to chose the "best case scenario" for each example.
For example, what if the first step returned this?
[...]
What it the rooms were larger (rather than the quick and dirty 2x3 rooms I made)?
[...]
Have each room / hallway keep a list of 'portals' - i.e points or zones connecting to the next room/area. Straight-line pathing can route dwarves from entrance to exit through a zone. No need to declare a specific path - the dwarf uses straight-line pathing through each zone given the constraint that zones are contiguous recatangles this can be done in realtime very fast.How will you define the cost of moving from one portal to another? How will you define the A* heuristic?
I covered that detail in my post (there was quite a bit of text though) - the cost to navigate through a rectangular zone portal => portal would be the dist from portal->portal in the zone, since zones are defined as openly connect rectangles this is a good estimate of the path cost. That would be added to the "path so far" for the graph A* is searching.Have each room / hallway keep a list of 'portals' - i.e points or zones connecting to the next room/area. Straight-line pathing can route dwarves from entrance to exit through a zone. No need to declare a specific path - the dwarf uses straight-line pathing through each zone given the constraint that zones are contiguous recatangles this can be done in realtime very fast.How will you define the cost of moving from one portal to another? How will you define the A* heuristic?
I covered that detail in my post (there was quite a bit of text though) - the cost to navigate through a rectangular zone portal => portal would be the dist from portal->portal in the zone, since zones are defined as openly connect rectangles this is a good estimate of the path cost. That would be added to the "path so far" for the graph A* is searching.Have each room / hallway keep a list of 'portals' - i.e points or zones connecting to the next room/area. Straight-line pathing can route dwarves from entrance to exit through a zone. No need to declare a specific path - the dwarf uses straight-line pathing through each zone given the constraint that zones are contiguous recatangles this can be done in realtime very fast.How will you define the cost of moving from one portal to another? How will you define the A* heuristic?
The heuristic for remaining distance to the target would be calculated in the normal A* way (with the additional check of 'is the target INSIDE this zone? - actually the dest zone ID could be determined before the search, and the zoneID of each searched zone compared to this ID), this will affect choice of zones to explore first (putting opened zones into the open list/heap). A* will search an arbitrary graph just as easily as it's set to search a grid.
The hierarchical structure I was talking about is just a method of using search trees as a data structure to organize the connectivity of nodes and speed up inter-node pathing. It doesn't have anything to do with intra-node pathing or zoning.
Basically, I was thinking of a Binary Search Tree as inspiration for it, and how that helps speed up searches.
Instead of making a standard connectivity grid for nodes, and then using a pathfinding program to search for a path, you create a tree data structure where connectivity is recorded in the pointers from one branch in the tree to the next.
Searching a tree data structure is much easier than trying to pathfind through them, so it can abstractly find a set of nodes to path through very, very quickly with the minimum possible number of memory fetching.
The data structure itself would kind of get bloated with pointers, depending on how you want to set it up - you basically can trade memory for speed and making better pathing decisions.
However, as I said before, this is talking solely about how to figure out which nodes to transverse once you have already set up the map, and doesn't even handle the size or shape of the nodes or intra-node pathing or anything besides the highest-level abstract pathing between nodes.
I think the room splitting algorithm is well defined don't forget the bitvector that defines nodes in a room. the bit vector is one of the major advantage.
example map(folded):room is defined from point t( 2,1) to point b (4,6) with a bit vector :Spoiler (click to show/hide)to add 1,3 all we need to do is change t to 1,1 and then grow and regenerate the bit vector . It might be easier to create a new room and then merge it. the new room bit mask is:Spoiler (click to show/hide)When the other points are dag out it's just a matter of setting bits. when you wall off the room you can clear bits and at some point shrink the room (not really critical). with a bitmask you can get an O(1) answer if a node is in a room .Spoiler (click to show/hide)
It might be smart to create 3d rooms and there is nothing stopping you from doing it with this model. It's also scalable to infinity so if your map becomes complicated you can split it farther by grouping its rooms into regions.
Anyways As I said the room splitting model a tad complicated (it's not that bad though most of it is already well defined). I think we should be aiming for path caching first( I have a working simulator) and we might be able to optimize it enough to make it adequate . Path caching is super easy and it can be user guided . If the user want to abuse it to confuse goblinite with silly waypoints he'll just get FPS drops.
There's a lot more to rooms than just squares. What about ramps? How about connections and shapes? If there isn't an arbitrary pre-set size cutoff, how will a room know when to split?The ramp just means a path upwards the bitmask is just to say if the node is in a room or not. There is no problem with overlapping rooms and they would never cover the same nodes. You can even define a room within a room. The spliting size should be big enough to be useful but small enough that you won't make path search too complex.
If you try to split based off of 1-2 tile wide passageways, what if a 1-2 tile wide passageway is dug out a series of times in a small room, creating many smaller, misshapen "rooms" within one larger room? This would end up with fewer tiles per room than an arbitrary size. Also, I don't see how just having a bit mask makes determining paths O(1)... Or the fact that the node structure is defined using a bit vector means anything at all.I didn't talk about O(1) path finding but it's possible in a room system. I was talking about O(1) validation: "is the point in the square and is it's bit set.". I'm not sure how you'll search your start and destination rooms but those are not that bad even if you use a linear search.
This is the kind of optimizations i'll leave for later. In general if room structure changes I'll regenerate it - it's not as bad as you think in terms of runtime.
Okay, so the node area is stored as a map of boolean values... ... How ELSE would you do it?
Also, you say "to add 1,3 all we need to do is add 1,1 and grow and regenerate the bit vector" What exactly is this growing and regeneration? Just how big of an area are you going to rebuild with every newly created tile / newly walled off tile?
For that matter, path caching is most certainly not the way to go, for several reasons mentioned... Also, not mentioned is that combining these two methods is functionally impossible, since ideally all zones would be invisible to the player and automatically generated, thus setting waypoints would have no effect on the overall path algorithm used because it is not used on actual tiles, but groups of them -- unfortunately this also affects the useful traffic designations, but I think the FPS gain would be worth it. The other problem with path caching is that the overhead of caching paths, with the significantly reduced worst case scenario of the node grouping algorithms, may actually exceed the possible gains simply because the sheer number of paths needing to be cached.
Also, what you are doing there seems to be using the same zone theory and simply letting the player designate "zone" areas by using waypoints -- since the waypoints are in fact not even being used to cache paths anymore, if a dwarf is not standing exactly on top of the waypoint, he cannot use a cached path. Are you trying to cache paths starting from all points within a certain distance from the waypoint? Because that would quickly become exponentially more complicated...
The intent of my post was to create discussion on the potentially BETTER algorithm -- how to create the convex polyhedrons used within the navmesh algorithm, which is significantly more complex than just creating arbitrarily shaped rooms.
The problem is, as stated in my (probably TL;DR) post, in creating the zones in the first place. While it is relatively simple to flood fill random areas until there are no more rectangles to be had, fortresses aren't built all at once, they're dug out or constructed one tile at a time by dwarves who don't enjoy digging things out in a meaningful manner. Obviously, you need to attempt to merge the newly opened tile with nearby rectangles, or, conversely, remove the now-closed tile and split the rectangle up into smaller ones. However, I can't think of any suitably fast ways to do this, and no conclusive algorithms have really been put forth in this thread. (I spent most of my free time before posting consolidating ideas in my head to solidify Niseg's idea, since it is significantly easier to implement)
The problem is, as stated in my (probably TL;DR) post, in creating the zones in the first place. While it is relatively simple to flood fill random areas until there are no more rectangles to be had, fortresses aren't built all at once, they're dug out or constructed one tile at a time by dwarves who don't enjoy digging things out in a meaningful manner. Obviously, you need to attempt to merge the newly opened tile with nearby rectangles, or, conversely, remove the now-closed tile and split the rectangle up into smaller ones. However, I can't think of any suitably fast ways to do this, and no conclusive algorithms have really been put forth in this thread. (I spent most of my free time before posting consolidating ideas in my head to solidify Niseg's idea, since it is significantly easier to implement)
Actually, I have covered that (http://www.bay12forums.com/smf/index.php?topic=76278.msg2097555#msg2097555). :)
But people don't like to give my method any merit, despite the fact that it's the only way that even makes sense. We go side tracked on this "bitmask" think which is pointless and useless. All that's really doing is covering how the navigation mesh is stored in memory (which is irrelevant) and not how it's built or used.
snipThe ramp just means a path upwards the bitmask is just to say if the node is in a room or not. There is no problem with overlapping rooms and they would never cover the same nodes. You can even define a room within a room. The spliting size should be big enough to be useful but small enough that you won't make path search too complex.
If you try to split based off of 1-2 tile wide passageways, what if a 1-2 tile wide passageway is dug out a series of times in a small room, creating many smaller, misshapen "rooms" within one larger room? This would end up with fewer tiles per room than an arbitrary size. Also, I don't see how just having a bit mask makes determining paths O(1)... Or the fact that the node structure is defined using a bit vector means anything at all.I didn't talk about O(1) path finding but it's possible in a room system. I was talking about O(1) validation: "is the point in the square and is it's bit set.". I'm not sure how you'll search your start and destination rooms but those are not that bad even if you use a linear search.
smaller rooms are not a problem the can be group into 1 bigger room that contains them. The bitmap allows any shape rooms which makes it very flexible in terms of adding nodes while still having a "square" shape which make it easy to tell if the point is within it or not.
This is the kind of optimizations i'll leave for later. In general if room structure changes I'll regenerate it - it's not as bad as you think in terms of runtime.
Okay, so the node area is stored as a map of boolean values... ... How ELSE would you do it?
Also, you say "to add 1,3 all we need to do is add 1,1 and grow and regenerate the bit vector" What exactly is this growing and regeneration? Just how big of an area are you going to rebuild with every newly created tile / newly walled off tile?
For that matter, path caching is most certainly not the way to go, for several reasons mentioned... Also, not mentioned is that combining these two methods is functionally impossible, since ideally all zones would be invisible to the player and automatically generated, thus setting waypoints would have no effect on the overall path algorithm used because it is not used on actual tiles, but groups of them -- unfortunately this also affects the useful traffic designations, but I think the FPS gain would be worth it. The other problem with path caching is that the overhead of caching paths, with the significantly reduced worst case scenario of the node grouping algorithms, may actually exceed the possible gains simply because the sheer number of paths needing to be cached.
Also, what you are doing there seems to be using the same zone theory and simply letting the player designate "zone" areas by using waypoints -- since the waypoints are in fact not even being used to cache paths anymore, if a dwarf is not standing exactly on top of the waypoint, he cannot use a cached path. Are you trying to cache paths starting from all points within a certain distance from the waypoint? Because that would quickly become exponentially more complicated...
I was also skeptical about the path caching method at first till I kept looking at it. I explained how it works in previous pages. if you want to get to S->D you can do it through 2 waypoints w1 and w2 which have a full path cache then the only thing you need to do is find the closest waypoints to S and D and find paths to them from S and D. You might think it's not worth it and it's memory consuming but with good waypoint placement you can reduce the number of nodes visited from 60% to 5%. keeping the paths to the waypoint short can improve the pathfinding algorithm complexity by a factor of 10.
Adding waypoint based pathfinding navigation is very easy to do and the gains from it would be major. I know that room spliting is a better system but it would take us some time to make it work.
The intent of my post was to create discussion on the potentially BETTER algorithm -- how to create the convex polyhedrons used within the navmesh algorithm, which is significantly more complex than just creating arbitrarily shaped rooms.
constructing nav mesh seems complicated and It could have too much memory and overhead use in case of many "teeth" .
I'm counting here over 12 nodes created for a mesh and that's a lot of data . Node grouping can do it in 1 or 2. Other than that those meshes are usually used to convert open areas into a graph which is navigated with A*. Those polygons are usually also hand drawn.
If you want to reach from S to D and want to use a streight line point 1 is blocked, 2 and 3 are passable 4 is blocked and 5 is passable .
Actually, I have covered that (http://www.bay12forums.com/smf/index.php?topic=76278.msg2097555#msg2097555). :)
But people don't like to give my method any merit, despite the fact that it's the only way that even makes sense. We go side tracked on this "bitmask" think which is pointless and useless. All that's really doing is covering how the navigation mesh is stored in memory (which is irrelevant) and not how it's built or used.
So you're saying that it's a method of searching through zones created by other means? I.e. we can use it on whichever grouping method other come up with? In that case, it's pretty cool, even though I don't really understand it.
In this vein, a short while after editing my wall of text for the second time, I realized that you can actually re-apply Niseg's algorithm on top of itself -- that is, group a cube of cubes of tiles into cubes of nodes, and search those, and create a massive tree structure that lends itself to recursive use of A* -- this would allow both the optimality of 2x2x2 cubes, and the abstraction and swiftness of 16x16x16 cubes, and also possibly make the idea of BFSing for the nearest (larger) node that contains a target material for item searching much more feasible, by then simply using nearest manhattan distance on a list of all items within that large node. There would be additional overhead for both, of course, but I believe it would be worth it, due to the sheer amount of pathfinding done in a mature fortress.
Essentially, take the tile to be added to the nodes, compare with neighboring nodes, find the largest it can merge with and still maintain a convex shape (restricting the algorithm to 45 degree angles, if necessary, to allow for non-square nodes), then attempt to merge that node with its neighbors (repeat as necessary).
A nav mesh is a special case of node grouping where the rooms have a shape of some polygon. polygons means some floating point stuff and complex operations like division and multiplication but it might not be that bad.
A Nav mesh uses "convex polygons" and triangles so I guess we can do something like that . I'm still not sure how we'll cover all the nodes with shapes. "teethed " regions would be majorly problematic.
little example:I'm counting here over 12 nodes created for a mesh and that's a lot of data . Node grouping can do it in 1 or 2. Other than that those meshes are usually used to convert open areas into a graph which is navigated with A*. Those polygons are usually also hand drawn.Spoiler (click to show/hide)
I think that with a mesh you might have the problem that maintaining it would be complicated and as you dig through your port you get crazy shapes and the nav mesh generator would keep trying to fit those polygons in which would be counter productive. I can try to write a simulation for it but it would take some research. I haven't found any source code that relates to nav mesh generation and its dynamic maintenance . I might want to look at RTS or something.
I'm not a big expert in discrete math and graph algorithms . I just know the basic and how to put things together. If you give me code I can read it and understand how it works.I did find some stuff on the internet. As I said I'm going to perfect my waypoint navigator before switching an approach .
You are welcome to write some source code in any language or show me an existing project that does automatic navmesh generation. I don't think it's worth the trouble but I was previously a big skeptic of the path caching approach and now became an advocate of it. It's not as memory intensive as you think and its gains in CPU time are huge.
As I said before A* can be fooled to go the wrong way. This is especially useful if you want to travel long distances. I made my program A* rather than using identical waypoint because it would be silly to do it and I observed some crazy stuff( I can probably fix it just figured it out ;)).
Another approach you can take in pathing is to assume you can get anywhere in a straight line and then deal with obstetrical . This generally assumes that if you go toward your target you'll reach it especially if it's on the same level. If you can fly this is what you want to do .
example (http://niseg.0adz.com/test_maze.html?maze=v010B0B1042084508214520C0910204401BFF1
link):If you want to reach from S to D and want to use a streight line point 1 is blocked, 2 and 3 are passable 4 is blocked and 5 is passable .Spoiler (click to show/hide)
A* complexity of this problem is 21. Using my program I can calculate how much complexity it would take to go around the obstacles. S to 2 = 4, 3 to 5 = 18. This yields higher complexity so it's not always good especially for walker. What a walker can do instead of trying to go around obstacles is think other straight paths from nodes nearby to like the lower case one. The problem with walker is that it's still trying to shoot through a needle hole but in open areas you can get to your target fairly fast. The other issue with A* is the amount of overhead in the algorithm and visiting a node has a lot more involved than checking it's passable.
I'll have to respond to Talonj later I currently don't have the time ;).
Kohaku:
Doesn't your extra storage at each level in the tree negate any gains from having a tree structure in the first place?
And won't the resulting paths be silly when the shortest path is a cross-branch step? For a simple example, consider a map that is only one huge ring-shaped tunnel (or series of rooms). Opposite the root node in the ring will be two nodes which are only connected through the root node - so the path found will go all the way around the ring unnecessarily?
Pardon me if I've misunderstood, but it seems like you're trying to squeeze performance out of pathing that is provably theoretically impossible - unless the map is *actually* a tree, topologically!
You're confusing storage with processing. Storage we have plenty of, processing we're using too much of.You misunderstand me; I meant that the extra storage has to be searched as well for each node, costing CPU. Even if it's a hash map, if it has to be done for every node it's still going to affect the time complexity.
By storing the data in the tree you trade away CPU usage for more RAM footprint.
Actually, I think I've thought of a much simpler/better way to explain what this tree system would represent.Yeah, this is the essence of hierarchical pathfinding, and it is pretty much what we do as humans when trying to plan how to get somewhere on a large scale.
Think of your address. Let's assume you want to get somewhere. Let's say, oh, 123 Sesame Street, which is in New York City, which is in New York, which is in The United States of America, which is on Earth, which is in the Sol System, which is in The Milky Way Galaxy.
So, if we ask the computer "Can you tell me how to get to Sesame Street?" (sorry, sorry!) we start by asking, "Are we on Sesame Street already?" "No." OK, then, we have to search a broader area. We know that Sesame Street is in New York City, so we have to ask, "Are we in New York City already?" "No." Then we have to look broader still, "Are we in New York State already?" "No." Go further out, "Are we in the USA already?" "Yes." Well, OK, then, we only have to look as far as traveling inside the USA, and don't have to ask ourselves how to get to the Sol System or rent a space ship or anything.
From there, we can tell that we are in state , and need to travel on the interstate/national level to get to the New York State area, then into the New York City area on a state level, then onto Sesame Street on a city level, then to the specific address of Sesame Street want to get to on a street level.
This is why this isn't a matter of local pathfinding - it just assumes something else handles local pathfinding for it. This works better for the longest-range pathfinding, and tells the local pathfinding to stay within the borders of one locality when looking for a path that is within one relatively-sized area instead of another.
You misunderstand me; I meant that the extra storage has to be searched as well for each node, costing CPU. Even if it's a hash map, if it has to be done for every node it's still going to affect the time complexity.
Except, of course, in that scheme nothing needs to be stored because the hierarchical structure is implicit. Not so in Kohaku's scheme. If each square at each scale had to keep an explicit list (or hash table) of all the smallest-scale squares that are in it, it wouldn't look so nice anymore.You misunderstand me; I meant that the extra storage has to be searched as well for each node, costing CPU. Even if it's a hash map, if it has to be done for every node it's still going to affect the time complexity.Now imagine that every 10 squares there's a thick border. And every hundred a huge dark border even more recognizable than the one every 10. You realize that your start and end locations are not only not in the same 10-square, they're not even in neighboring 100 squares! So rather than counting each tile you generalize. You count hundred-squares. You find that there are 4. Next you count the partial hundred-squares using the ten-squares. There's 6 of those, two on one end, four on the other. Finally you count the last remaining distance. 13. 9 tiles on one end, four on the other. How far's the distance?
One, two, three, four....
##################################
###########+++++##################
###########+++++##################
#######+++#+++++#++++++++#########
#######+++#+++++#++++++++#########
#######+++#+++++#++++++++#########
#######++++++++++++++++++#########
###########+++++#++++++++#########
###########+++++#++++++++#########
###########+++++#++++++++#########
###########+++++##################
###########+++++##################
###########+++++##################
###########+++++##################
######++++#+++++##################
######++++#+++++##################
######++++++++++##################
######++++#+++++##################
######++++#+++++##################
######++++#+++++##################
######++++#+++++##################
######++++#+++++##################
######++++#+++++##################
######++++#+++++##################
######++++#+++++##################
######++++#+++++##################
######++++++++++#+++##############
######++++#+++++#+++##############
###########+++++++++##############
###########+++++#+++##############
###########+++++#+++##############
###########+++++##################
###########+++++##################
#####################################################################
###########44444###################
###########44444###################
#######333#44444#11111111##########
#######333#44444#11111111##########
#######333#44444#11111111##########
#######333222222222222222##########
###########55555#77777777##########
###########55555#77777777##########
###########55555#77777777##########
###########55555###################
###########55555###################
###########55555###################
###########55555###################
######<<<<#55555###################
######<<<<#55555###################
######<<<<666666###################
######<<<<#:::::###################
######<<<<#:::::###################
######<<<<#:::::###################
######<<<<#:::::###################
######<<<<#:::::###################
######<<<<#:::::###################
######<<<<#:::::###################
######<<<<#:::::###################
######<<<<#:::::###################
######<<<<888888#===###############
######<<<<#?????#===###############
###########?????9999###############
###########?????#>>>###############
###########?????#>>>###############
###########?????###################
###########?????###################
###################################
#####################################################################
##+#+#+#+#+#+#####################
#++++++++++++#####################
##################################
##################################
##################################
##################################
##################################
##################################
##################################
##################################
##################################
##################################
##################################
##################################
##################################
##################################
##################################
##################################
##################################
##################################
##################################
##################################
##################################
##################################
##################################
##################################
##################################
##################################
##################################
##################################
##################################
##################################
#####################################################################
##1#2#3#4#5#6######################
#718293a4b5c6######################
###################################
###################################
###################################
###################################
###################################
###################################
###################################
###################################
###################################
###################################
###################################
###################################
###################################
###################################
###################################
###################################
###################################
###################################
###################################
###################################
###################################
###################################
###################################
###################################
###################################
###################################
###################################
###################################
###################################
###################################
###################################
#####################################################################
#######++++++++++#################
######+++++++++#+#################
######+#++#++#+++#################
######+++++++++++#################
######+++++++#+++#################
######+++++++++++#################
######++++++++++##################
######+++++++++++#################
######+++#+++++++#################
#######++++++++++#################
######+++++++++#+#################
######+++++++++++#################
######+++++#+++++#################
######+++++++++++#################
######++#+++#++++#################
######++++++++++##################
######++++#++++++#################
######+++++++++++#################
######+++++++++#+#################
######++++#++++++#################
######+++++++++++#################
#######++++++++++#################
######++++++++#++#################
##################################
##################################
##################################
##################################
##################################
##################################
##################################
##################################
##################################
#####################################################################
#######1111111111##################
######222222222#3##################
######4#55#66#773##################
######48888888883##################
######4999999#::3##################
######4999999<<<3##################
######4999999<<<###################
######4999999<<<;##################
######4??#>>>>>>;##################
#######??=======;##################
######AAAAAAAAA#;##################
######AAAAAAAAA@;##################
######DDDDD#CCC@;##################
######DDDDDBBBB@;##################
######NN#FFF#GG@;##################
######NNEEEEEEE@###################
######NNHH#JJJJ@K##################
######NNHHIIIII@K##################
######NNHHIIIII#K##################
######NNHH#LLLLLK##################
######NNHHMMMMMMK##################
#######OOOOOOOOOK##################
######PPPPPPPP#QK##################
###################################
###################################
###################################
###################################
###################################
###################################
###################################
###################################
###################################
###################################
#####################################################################
######++++++++++##################
######++++++++++##################
######+++++++++###################
######+++++++++###################
######+++++++++###################
######+++++++++###################
######++++++++####################
######+++++++#####################
######+++++++#####################
######+++++#######################
######++++########################
######+++#########################
######++##########################
######++##########################
######+###########################
######+###########################
##################################
##################################
##################################
##################################
##################################
##################################
##################################
##################################
##################################
##################################
##################################
##################################
##################################
##################################
##################################
##################################
#####################################################################
######2222222222###################
######2222222222###################
######333333333####################
######333333333####################
######333333333####################
######333333333####################
######11111111#####################
######5555555######################
######5555555######################
######44444########################
######6666#########################
######777##########################
######99###########################
######99###########################
######8############################
######8############################
###################################
###################################
###################################
###################################
###################################
###################################
###################################
###################################
###################################
###################################
###################################
###################################
###################################
###################################
###################################
###################################
###################################
###################################The problem is to create nodes while digging out rooms. Niseg's idea makes it easy, because there is no prerequisite for a tile being included in a node, you just check for an adjacent node and add to it. However, with this idea, unless a highly efficient algorithm to create and merge nodes is used, the overhead may outweigh the benefit, and the benefit may be mitigated by highly suboptimal shapes.My code is still utterly unoptimized and the complexity of the merge function is O(n) in the worst case where n is the number of connections of the node where the tile is merged (O(1) if the digged tile can't be merged). The only real problem of this method is to find out how to (very) efficiently slice the map (see the "classic fortress" the main hall is cut in 8 parts)
Except, of course, in that scheme nothing needs to be stored because the hierarchical structure is implicit. Not so in Kohaku's scheme. If each square at each scale had to keep an explicit list (or hash table) of all the smallest-scale squares that are in it, it wouldn't look so nice anymore.
Doesn't matter if you're explicitly storing larger chunks or implicitly knowing what they are. The point is that A* takes fewer steps. The reason this works is because every explicitly defined area is a convex solid, meaning that from any point within its boundaries to any other point within its boundaries there exists an uninterrupted strait line (of unknown length) between them. A* doesn't need to check of the path exists on the tile level so long as it exists on the "node map" level.Your answer has nothing to do with the tree structure or the hash tables.
Doesn't matter if you're explicitly storing larger chunks or implicitly knowing what they are. The point is that A* takes fewer steps. The reason this works is because every explicitly defined area is a convex solid, meaning that from any point within its boundaries to any other point within its boundaries there exists an uninterrupted strait line (of unknown length) between them. A* doesn't need to check of the path exists on the tile level so long as it exists on the "node map" level.Your answer has nothing to do with the tree structure or the hash tables.
We're still talking about pathfinding, right? Not about searching for a single node?Doesn't matter if you're explicitly storing larger chunks or implicitly knowing what they are. The point is that A* takes fewer steps. The reason this works is because every explicitly defined area is a convex solid, meaning that from any point within its boundaries to any other point within its boundaries there exists an uninterrupted strait line (of unknown length) between them. A* doesn't need to check of the path exists on the tile level so long as it exists on the "node map" level.Your answer has nothing to do with the tree structure or the hash tables.
Doesn't matter. The data structure used is one of generalization. A tile always knows which node it is in in the tree/hash/mesh* thereby ignoring the "search the data structure" part of your worry. Of course, even that doesn't matter, as searching a data structure of points for a given point is trivial compared to the time that is saved by using the data structure.
*For trees, it actually doesn't matter, it can be determined because the data structure is a god damn tree. If you don't know how to search a tree, and why it takes O(n) time to search, you don't know how a tree is set up.
Now, in order to search this tree, you start from the starting node, and search the hash list of branches and leaves connected to the starting node. If the destination node is not in that list, you go down a node on the tree, and search the lower node that connects to the starting node, and see if you can reach the destination node by only going up from there. If that doesn't work, you keep going down the tree all the way to the roots until you can find a path to the destination node.Now tell me how the searching of data structures doesn't impact performance in this algorithm.
Once you find a branch with a connection to the destination node, you just go up the tree, testing which branches will have connections to the destination node, until you finally strike the destination node, itself.
I am in the mood of writing some code, so I made the "merge node" algorithm, which I used to slice in rectangles some maps (I add all the walkable tiles one by one, like if it was a digged tile).
here is what it gives on some classic maps.
I'm not sure I understand your struct , do you define a node by a (at most) 10 edges shape? if so, what are the 2 corners?
Ok I looked at some of your code I think you should have used an array of structs instead of 3d array . Well doesn't matter.
my idea was to use this data type for node:Spoiler (click to show/hide)
This can save nodes in any shape even overlapping rooms with max size of 256. There are more useful function like growing and shrinking it to the appropriate room size (adding rows and columns at the edges) .
##################
##+#+#+#+#+#######
#++++++++++#######
##################
We're still talking about pathfinding, right? Not about searching for a single node?
I quote:QuoteNow, in order to search this tree, you start from the starting node, and search the hash list of branches and leaves connected to the starting node. If the destination node is not in that list, you go down a node on the tree, and search the lower node that connects to the starting node, and see if you can reach the destination node by only going up from there. If that doesn't work, you keep going down the tree all the way to the roots until you can find a path to the destination node.Now tell me how the searching of data structures doesn't impact performance in this algorithm.
Once you find a branch with a connection to the destination node, you just go up the tree, testing which branches will have connections to the destination node, until you finally strike the destination node, itself.
I submit: Yes, if you restrict your pathfinding to only considering this star-shaped topology of your map, ignoring any cross-connections, then you can find a path faster like Kohaku says. But
a: Your paths can be arbitrarily bad and
b: Your time cost will be multiplied by a hash table (or similar) lookup (since it occurs at every step) and
c: Your space cost will be much increased
b and c would be mitigated if we had something like the square-in square subdivision you suggested earlier - then a couple of comparisons would do and no extra storage would be needed. But that carries the extra problem that not all space in each super-square is connected. That's been discussed earlier in this thread; you could split each node into multiple ones representing connected subcomponents. This throws the best-case complexity out the window however.
believe me 10 edges is more than enough. rooms with too many can be merged or sliced.I'm not sure I understand your struct , do you define a node by a (at most) 10 edges shape? if so, what are the 2 corners?
Ok I looked at some of your code I think you should have used an array of structs instead of 3d array . Well doesn't matter.
my idea was to use this data type for node:Spoiler (click to show/hide)
This can save nodes in any shape even overlapping rooms with max size of 256. There are more useful function like growing and shrinking it to the appropriate room size (adding rows and columns at the edges) .
how can it store this shape for exemple?(which is convex)(edit: forget this , but still how do you represent this shape and whith how many nodes?)Code: [Select]##################
##+#+#+#+#+#######
#++++++++++#######
##################
And more importantly how do you know if you can add a tile to a shape (does the new shape will still be convex?).
But my main goal was to make the function that dinamically change the graph when you add (dig) a new walkable tile not the room slicing function. I just tried to slice the map by digging 1 tile by 1 tile, and it was surprisingly not so bad and pretty fast for a first try.
A. is probably not as bad as you think it might be, and it may simply be worth the loss. As long as the nodes are of generally similar sizes, you should generally see nodes that are equidistant from wherever the root node is should be roughly similar tiers on the tree, unless the nodes have to take some very winding detours. In that case, the path that took the long detours will naturally already be fairly high on the tree, while the straighter path will be low on the tree. The low parts of the tree should take precedence in gaining leaves and branches for itself in the purpose of building the tree. Using the last method I mentioned ("duplicate-branches" let's call it), the one that takes up extra memory, should potentially solve all the problems with un-optimized routes. (And remember, we want to optimize for performance and memory use more than we necessarily want to optimize for finding the shortest path, so long as it isn't an unreasonably long detour.) I haven't actually tried to come up with some sort of nightmare case that would actually produce a real problem for the duplicate-branches, so it may be optimal, anyway.I sort of see before me a road system where all traffic between Pasadena and Seattle is routed through St. Louis...
B is true, but again, it's probably not the limitation you think it is - you are looking up the hash table in every node you visit to see if there is a direct path up the tree to find the node you are searching for. This is, however, not a problem. This basically just means we are doing another memory fetch per node we look at, while at the same time we are cutting down a cross-map search from a sub-geometric complexity to a logarithmic complexity. In other words, we're turning O(n^3) into O(log(2n)) where the 2 in the 2n is the extra looking up in the hash table. That's completely worth it in anything but the shortest of all pathfinding equations.I don't know enough about the complexity of hashes but won't the worst-case bite you occasionally? Anyway, you may be right on this one. Again, you could do without any hash table if the contents of a node were implicit (like with a quadtree, which is pretty much what Draco brought up before).
C is the real threat. As you say, however, it may just be easier to make multiple "levels" or "hierarchies" of data structures altogether to try to keep the size of each individual data structure down. (I say "levels" instead of "tiers" so as not to confuse the terminologies, here.) Because the complexity of those hash tables increases geometrically with the number of tiers in the tree, (and again, this complexity is geometric growth of memory consumption giving us logarithmic growth of processor power,) you can save on memory by making multiple levels of nodes.This hierarchical clustering is really independent of your tree-based search. Any search method can be used with it.
For example, in the "moving to another location on the Earth" example I was talking about earlier, you can organize individual nodes of buildings and streets, and conglomerate them together into a city, and you only have to do the tree search from the city level up to the planet level.
You can have fairly simple nodes that are conglomerated together on the next level of abstraction so that you have an area consisting of no more than some arbitrary number of nodes or some arbitrary amount of area where you can ensure relatively easy connectivity between that area's nodes, and then make that area of nodes the "city" which is the smallest unit in the tree data structure - hence, conglomerating 100 nodes into a "node area" that occupies one large-scale tree node.Sounds OK in principle, but how would it all be done more concretely?
The starting point and destination would then compare whether they are in the same node area or not, and if they are in the same area, you wouldn't have to use the large-scale tree at all.
You could work the small-scale area into being a tree configuration, as well. You simply need to make a list of known connections to the other areas, and pare them down to the ideal candidates. In a collection of smaller-scale nodes, where everything is conglomerated based upon being in proximity to one another, you will actually see your "A" concern a little less prominent, as well, since you can simply build the closest thing to a fractal "star" that you can get out of the nodes to make your small-scale tree.
You can also throw as many levels of abstraction into this as you ever deem necessary at that point - you can simply have some arbitrary cut-off of x-number of nodes in a tree that forces the jump to a new level of abstraction, allowing for arbitrary levels of abstraction, although this would make the address of each node become more complex, and require a vector to store it, rather than set data types.
A-B-C-D
| | | |
E-F-G-H
| | | |
I-J-K-L
I sort of see before me a road system where all traffic between Pasadena and Seattle is routed through St. Louis...
I don't quite follow how the "duplicate-branches" algorithm works. What precisely are you storing for each node in addition to the simpler version? Which stores, if I understand it correctly, a list of all nodes above it and a pointer to its immediate successors.
(Your use of up and down confused me before; I usually have parent nodes above the child nodes but at least I get you now)
In the first method, (let's use Wikipedia's page on trees for an illustration), let's assume that we found a path in that tree from the "5" node on the bottom left to the "9" node on the right. This would return a path of "5->6->7->2->5->9", but at the same time, 7 and 5 are connected, so you can cut out the path with 2 inside of it.
When making that original chain of nodes, you basically are only looking for going up and down the tree, not laterally - you go "down" the tree ("down" being towards the roots) until you find a route directly up the tree you can follow. To do this, you have a list of all the points "up the tree" from a given node. Once you have that chain, however, you can look for lateral shortcuts by simply comparing all the connections (up, down, or lateral on the tree) that allow a given node to bypass one or more steps in the chain.
This method has a complexity of an additional O(n^2/2) where n is the length of the chain you returned previously. It winds up with some extra memory calls, but should still be much faster than A*-ing the entire fort.
This will basically return you the previous path, but with a few shortcuts taken where they are found.
I don't know enough about the complexity of hashes but won't the worst-case bite you occasionally? Anyway, you may be right on this one. Again, you could do without any hash table if the contents of a node were implicit (like with a quadtree, which is pretty much what Draco brought up before).
This hierarchical clustering is really independent of your tree-based search. Any search method can be used with it.
One has to connect the different levels though - if I'm in St. Louis on the large-scale map, where exactly am I on the city map? How do I combine the costs from both levels? But this is for another subthread, really.
QuoteYou can have fairly simple nodes that are conglomerated together on the next level of abstraction so that you have an area consisting of no more than some arbitrary number of nodes or some arbitrary amount of area where you can ensure relatively easy connectivity between that area's nodes, and then make that area of nodes the "city" which is the smallest unit in the tree data structure - hence, conglomerating 100 nodes into a "node area" that occupies one large-scale tree node.Sounds OK in principle, but how would it all be done more concretely?
The starting point and destination would then compare whether they are in the same node area or not, and if they are in the same area, you wouldn't have to use the large-scale tree at all.
You could work the small-scale area into being a tree configuration, as well. You simply need to make a list of known connections to the other areas, and pare them down to the ideal candidates. In a collection of smaller-scale nodes, where everything is conglomerated based upon being in proximity to one another, you will actually see your "A" concern a little less prominent, as well, since you can simply build the closest thing to a fractal "star" that you can get out of the nodes to make your small-scale tree.
You can also throw as many levels of abstraction into this as you ever deem necessary at that point - you can simply have some arbitrary cut-off of x-number of nodes in a tree that forces the jump to a new level of abstraction, allowing for arbitrary levels of abstraction, although this would make the address of each node become more complex, and require a vector to store it, rather than set data types.
My work on path smoothing have shown major progress as you can see in this Maze (http://niseg.0adz.com/test_maze.html?maze=v02AgAgAQEQEEGQcJFQIIAxwAAAAAAMAAAAAwAAAPrmAQAAHAAAAAMAADAAwAAPAAAAAOAAgAACAQBBDAIAQDAEACDACAAhABAAIAAgABAAQAAQAIAAEAEAAAgCAAAIBAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA)(someone else drew it though). You can play with waypoint and do extra smoothing steps . The results are pretty good( you can even smooth A*) except for when there are loops which are caused by waypoints. I'll either use the loop searching function I'm working on and do smoothing afterward or improve the path smoothing to have a larger lookahead especially on the first iteration.
In the first method, (let's use Wikipedia's page on trees for an illustration), let's assume that we found a path in that tree from the "5" node on the bottom left to the "9" node on the right. This would return a path of "5->6->7->2->5->9", but at the same time, 7 and 5 are connected, so you can cut out the path with 2 inside of it.Here you're letting the shortcut lookup be O(1) and the construction of that lookup table O(n), I take it. That may be reasonable on average, though not worst-case I guess.
When making that original chain of nodes, you basically are only looking for going up and down the tree, not laterally - you go "down" the tree ("down" being towards the roots) until you find a route directly up the tree you can follow. To do this, you have a list of all the points "up the tree" from a given node. Once you have that chain, however, you can look for lateral shortcuts by simply comparing all the connections (up, down, or lateral on the tree) that allow a given node to bypass one or more steps in the chain.
This method has a complexity of an additional O(n^2/2) where n is the length of the chain you returned previously. It winds up with some extra memory calls, but should still be much faster than A*-ing the entire fort.
This would mean that, you would find a route that goes through St. Louis, and then you search for more direct paths by cutting out whatever "middlemen" you can, resulting in a much more direct route.Well, whether it's much shorter or merely cuts the very tip of the wedge next to St. Louis depends wholly on the coarseness of the map, doesn't it? If there are always at least two cities between the first and second "leg" of the trip, this modification won't make any difference.
This works well if there are only a few entry points into a sub-map. There are only so many ways to enter St. Louis (on a major highway at least). But it will be worthless if there are loads and loads of entry points, such as will be the case for a general quadtree square over a DF map. And for anything larger-scale than individual rooms, which *may* have only a few doors out of it, it will be a monumental task coming up with an algorithm to decide the right way to subdivide the map into a large-scale clustering which minimizes the number of entry points.This hierarchical clustering is really independent of your tree-based search. Any search method can be used with it.
One has to connect the different levels though - if I'm in St. Louis on the large-scale map, where exactly am I on the city map? How do I combine the costs from both levels? But this is for another subthread, really.
You can store tree-level paths "through" the tree. This means that you don't even have to path through entire lower-level trees you are pathing through, you just store the route, and always take that route.
If you're passing through St. Louis by taking the Interstate, you don't need to look at the individual city routes at all, you just need to stay on the Interstate heading on whatever direction you are heading.
Whoa, hold there. Let's assume without loss of generality that *all* the free space in the map is connected. What then? Just being connected can't be used as criterion for splitting space up - that would be meaningless! Space that isn't connected shouldn't be part of the same tree on *any* level!Sounds OK in principle, but how would it all be done more concretely?
Well, you just start with whatever convex cubes you wind up having from the node-creating function (that's beyond this discussion). Then you have to start stitching these pieces together.
You have two major paths to follow from there.
The first option is that you can start from geometric isolation:
This means starting with splitting the map into cubes of geographic areas, and then looking to make sure that all nodes in those cubes connect with one another, and splitting of any cubes which do not have connectivity. You then stitch together trees out of the nodes that are still in those geographic areas have connectivity, and then you build the next level of hierarchy as a way to get from one geographic area to the others.
The other option is that you can start from an arbitrary point somewhere in the "middle" of the map:Could you draw a picture of that? *scratches head* Does every subtree become a single node in the L2 tree or multiple nodes? If multiple, how is the L1 tree subdivided to make L2 nodes?
This works best with the innate nature of a tree data structure, upon further thought, since it relies upon some of its basic principles, and assumes some dynamic ability to shift to changing nodes.
Pick a node, any random node on the map.
Now, you have to start connecting all its adjacent nodes to it as branches, and start building a tree.
During this process, the tree needs to "balance" itself, which is a basic function of many trees. This means that the "root node" will change to be the node with the most roughly-equidistant leaf nodes hanging off of it. (This means that you don't want a lopsided tree, if a branch becomes larger than the rest of the tree, the start of that branch becomes the new root, and the old root becomes a branch of the new root.)
Once you hit a certain point of complexity, say ten tiers on the tree structure, it is time to build the next level of hierarchy. In this, the root node becomes not only a root node for the level-1 tree that we were building before, but also the root node of the level-2 tree, which acts as the geographical equivalent of moving from a city-level to a state-level of travel. Each of those other level-1 trees becomes filled out with new root nodes for their level-1 trees, based upon the fastest connection to the root node of the level-2 tree. Each of these new level-1 trees is now a branch of the level-2 tree. You then keep on going, populating the level-1 trees until they have to simply split off, and make a new level-1 tree which they are connected to.
No, not worst-case, really, but worst case can be very tricky to calculate.In the first method, (let's use Wikipedia's page on trees for an illustration), let's assume that we found a path in that tree from the "5" node on the bottom left to the "9" node on the right. This would return a path of "5->6->7->2->5->9", but at the same time, 7 and 5 are connected, so you can cut out the path with 2 inside of it.Here you're letting the shortcut lookup be O(1) and the construction of that lookup table O(n), I take it. That may be reasonable on average, though not worst-case I guess.
When making that original chain of nodes, you basically are only looking for going up and down the tree, not laterally - you go "down" the tree ("down" being towards the roots) until you find a route directly up the tree you can follow. To do this, you have a list of all the points "up the tree" from a given node. Once you have that chain, however, you can look for lateral shortcuts by simply comparing all the connections (up, down, or lateral on the tree) that allow a given node to bypass one or more steps in the chain.
This method has a complexity of an additional O(n^2/2) where n is the length of the chain you returned previously. It winds up with some extra memory calls, but should still be much faster than A*-ing the entire fort.
QuoteThis would mean that, you would find a route that goes through St. Louis, and then you search for more direct paths by cutting out whatever "middlemen" you can, resulting in a much more direct route.Well, whether it's much shorter or merely cuts the very tip of the wedge next to St. Louis depends wholly on the coarseness of the map, doesn't it? If there are always at least two cities between the first and second "leg" of the trip, this modification won't make any difference.
This works well if there are only a few entry points into a sub-map. There are only so many ways to enter St. Louis (on a major highway at least). But it will be worthless if there are loads and loads of entry points, such as will be the case for a general quadtree square over a DF map. And for anything larger-scale than individual rooms, which *may* have only a few doors out of it, it will be a monumental task coming up with an algorithm to decide the right way to subdivide the map into a large-scale clustering which minimizes the number of entry points.This hierarchical clustering is really independent of your tree-based search. Any search method can be used with it.
One has to connect the different levels though - if I'm in St. Louis on the large-scale map, where exactly am I on the city map? How do I combine the costs from both levels? But this is for another subthread, really.
You can store tree-level paths "through" the tree. This means that you don't even have to path through entire lower-level trees you are pathing through, you just store the route, and always take that route.
If you're passing through St. Louis by taking the Interstate, you don't need to look at the individual city routes at all, you just need to stay on the Interstate heading on whatever direction you are heading.
Whoa, hold there. Let's assume without loss of generality that *all* the free space in the map is connected. What then? Just being connected can't be used as criterion for splitting space up - that would be meaningless! Space that isn't connected shouldn't be part of the same tree on *any* level!Sounds OK in principle, but how would it all be done more concretely?
Well, you just start with whatever convex cubes you wind up having from the node-creating function (that's beyond this discussion). Then you have to start stitching these pieces together.
You have two major paths to follow from there.
The first option is that you can start from geometric isolation:
This means starting with splitting the map into cubes of geographic areas, and then looking to make sure that all nodes in those cubes connect with one another, and splitting of any cubes which do not have connectivity. You then stitch together trees out of the nodes that are still in those geographic areas have connectivity, and then you build the next level of hierarchy as a way to get from one geographic area to the others.
You have to divvy space up on the basis of choke points, or maximum convex regions or some other heuristic. Which one though?
QuoteThe other option is that you can start from an arbitrary point somewhere in the "middle" of the map:Could you draw a picture of that? *scratches head* Does every subtree become a single node in the L2 tree or multiple nodes? If multiple, how is the L1 tree subdivided to make L2 nodes?
This works best with the innate nature of a tree data structure, upon further thought, since it relies upon some of its basic principles, and assumes some dynamic ability to shift to changing nodes.
Pick a node, any random node on the map.
Now, you have to start connecting all its adjacent nodes to it as branches, and start building a tree.
During this process, the tree needs to "balance" itself, which is a basic function of many trees. This means that the "root node" will change to be the node with the most roughly-equidistant leaf nodes hanging off of it. (This means that you don't want a lopsided tree, if a branch becomes larger than the rest of the tree, the start of that branch becomes the new root, and the old root becomes a branch of the new root.)
Once you hit a certain point of complexity, say ten tiers on the tree structure, it is time to build the next level of hierarchy. In this, the root node becomes not only a root node for the level-1 tree that we were building before, but also the root node of the level-2 tree, which acts as the geographical equivalent of moving from a city-level to a state-level of travel. Each of those other level-1 trees becomes filled out with new root nodes for their level-1 trees, based upon the fastest connection to the root node of the level-2 tree. Each of these new level-1 trees is now a branch of the level-2 tree. You then keep on going, populating the level-1 trees until they have to simply split off, and make a new level-1 tree which they are connected to.
Nice interface.Thanx, It could be better but it's functional (does what it supposed to do with little gimmicks).
I pressed A* and got a slightly "off" path though, so I'm wondering: what is the actual cost function you're using? one step costs 1? That would explain the path I saw but that makes several of the heuristics inadmissible.there is currently no weights or adjustment to A* to fit DF exactly it's not really the point but I can add it along with traffic zones if I put my mind to it
Also, there's another heuristic that might be relevant:I can easily add that one it's pretty simple to add heuristic functions to my program.
sqrt(2)*max(abs(dx),abs(dy)) + (1-sqrt(2))min(abs(dx),abs(dy))
that is, the smallest distance possible if you may only walk at 45 degree increments (which is true for dwarfs in DF, though not for projectiles).
A sorted hash-table index, however, would be very good for a situation where changes are few but queries many, by binary-search methods. Each time you have to change the table, though you would have to insert each and every new item (binary-search for the pair just-above and just-below, by the search criteria being used, then shuffle the top 'half' upwards to make room) and remove each and every removal (reverse, by shuffling down the greater-thans). You could make a compromise system in which a limited number of null data points get left behind after splicing out a point so that there's a chance that a spliced-in item can sit in a handy null-point, but that does slow the searching down[3], there's always going to be the possibility that a number of shifts[4], and certainly while increasing the number of hash-points being stored there's going to be a scarcity of null-spots and you're going to be increasing the table's size just as if it wasn't a null-filled version. Never mind that you may end up storing an N point hash table in a 2N or more length hash table, which may again eat into any of the efficiencies you get.
I'm not saying that Hash Tables are bad, and as a Perlite I tend to (over?-)use them myself for convenience alone, but the purpose you're putting the hash-table towards might not be particularly conducive to the structure. There isn't a magical 'black box' function that will let you store and retrieve hash values (including references) under a hash key in a straight O(c) number of CPU ticks. You may even be optimising something by using hash lookup that was actually more optimal, despite itself, than the hash-maintenance and using process ends up being.
Sorry, I didn't remember that post. (How long ago was it? This thread has kind of gone on for a couple months...)
#define EMPTY NULL
int removed=0;
#define REMOVED (void *) (&removed);
int size=0;
void ** table;
init(int n)
{
int i=0;
size=1<<n;
table=malloc(size);
for (i=0 ;i<size;++i) table[i]=EMPTY;
}
#define HASHFUNCTION(a) (a) /* find something better than this and replace*/
hash(int val)
{
return (HASHFUNC(val))&(size-1);
}
int insert(void * val)
{
int i,j;
i=*((int *) val);
i=hash(i);
for(j=0;j<size;++j)
{
if(table[i]==EMPTY|| table[i]==REMOVED)
{table[i]=val;return 1;}
i=(i+1)&(size-1);
}
return 0;
}
void * find(int key)
{
int i,j;
i=hash(key);
for(j=0;j<size;++j)
{
if(table[i]==EMPTY)
return NULL;
if(table[i]!=REMOVED)
return table[i];
i=(i+1)&(size-1);
}
}
I happen to remember most of the common data structures and I hope my coworkers at least understand how to use them ;).
Why shouldn't it be possible to have the computer calculate some lines that follow the best path fairly closely, and then the dwarf just goes along those lines and doesn't have to recalculate until it reaches the end of the line? Then the dwarf doesn't have to figure out where it's going again every time it takes a step. It'd make a 200-dwarf fort a snap.how do you know if a line follow a path if you don't know the path?
Why shouldn't it be possible to have the computer calculate some lines that follow the best path fairly closely, and then the dwarf just goes along those lines and doesn't have to recalculate until it reaches the end of the line? Then the dwarf doesn't have to figure out where it's going again every time it takes a step. It'd make a 200-dwarf fort a snap.My Path caching scheme does exactly that!
how do you know if a line follow a path if you don't know the path?
Why shouldn't it be possible to have the computer calculate some lines that follow the best path fairly closely, and then the dwarf just goes along those lines and doesn't have to recalculate until it reaches the end of the line? Then the dwarf doesn't have to figure out where it's going again every time it takes a step. It'd make a 200-dwarf fort a snap.
This would mean that, you would find a route that goes through St. Louis, and then you search for more direct paths by cutting out whatever "middlemen" you can, resulting in a much more direct route.I was talking about only the tree-based pathfinding here, without also imposing the hierarchical scheme you suggested subsequently. If all you have are cities, not states or any larger groups, you'll still have the problem I describe. Just clarifying.QuoteWell, whether it's much shorter or merely cuts the very tip of the wedge next to St. Louis depends wholly on the coarseness of the map, doesn't it? If there are always at least two cities between the first and second "leg" of the trip, this modification won't make any difference.
Except it doesn't just trim off the very tip. It compares every step of the journey for a shorter route between every point along the line. This means that it will only path up to St. Louis if it has to go that far to find the correct relative distances in the tree for comparison, and then it could theoretically lop off that pathfinding all the way down to a simple path directly from one city to the other.
Let's take an example of two cities on opposite sides of a state boarder. When you want to go across that state border into the next town, you would be transitioning not just cities, but also states. This means you hop up from a street level to a city level to a state level to a national level of travel, then zoom back down to the city and street level. But you don't need to travel back to state capitals to get there, you just need to check for the best lateral connection on the tree, which would involve simply driving down the nearest road across the border.
No, you misunderstand. I really meant passing-through. If St. Louis has only, say, 10 major entry points you need to store 45 costs. All well and good. But what about the state of Missouri? It will likely have hundreds of entry points, meaning thousands of costs to pre-compute and store.This works well if there are only a few entry points into a sub-map. There are only so many ways to enter St. Louis (on a major highway at least). But it will be worthless if there are loads and loads of entry points, such as will be the case for a general quadtree square over a DF map. And for anything larger-scale than individual rooms, which *may* have only a few doors out of it, it will be a monumental task coming up with an algorithm to decide the right way to subdivide the map into a large-scale clustering which minimizes the number of entry points.
This goes back to that hierarchical pathfinding thing I was talking about about ten pages earlier in the thread.
You can draw up all the pathways in and out of a node, but you really don't need all of them. As long as you are pathing "through" St. Louis, and not actually going to some point inside of it, it doesn't matter that there are routes through St. Louis that aren't the Interstate, as long as the Interstate is the BEST path, that's all you need to remember.
You can check for plenty of routes from one point to another, but you only need to store the best route from one exit to another exit. You can keep storing the different entry points, but these would only matter if you were looking for a specific point inside of St. Louis you wanted to reach where it might make a difference.
That's not admissible if the step cost is 1. 4 steps diagonally would cost 4 in reality, but that heuristic is higher (4*sqrt(2)). The heuristic must be equal or lower. Same goes for some of the others.I pressed A* and got a slightly "off" path though, so I'm wondering: what is the actual cost function you're using? one step costs 1? That would explain the path I saw but that makes several of the heuristics inadmissible.there is currently no weights or adjustment to A* to fit DF exactly it's not really the point but I can add it along with traffic zones if I put my mind to it
The current default heuristic function is a vector magnitude sqrt(dx2 +dy2 ) it should be admissible i might want to Math.floor it to avoid floating point .
Also, there's another heuristic that might be relevant:I can easily add that one it's pretty simple to add heuristic functions to my program.
sqrt(2)*max(abs(dx),abs(dy)) + (1-sqrt(2))min(abs(dx),abs(dy))
that is, the smallest distance possible if you may only walk at 45 degree increments (which is true for dwarfs in DF, though not for projectiles).
Sure, disconnected trees aren't the problem. But you can't use connectedness as the criterion for splitting up space like in the quote. You have to make something else up, some heuristic - there's no free lunch.The first option is that you can start from geometric isolation:Whoa, hold there. Let's assume without loss of generality that *all* the free space in the map is connected. What then? Just being connected can't be used as criterion for splitting space up - that would be meaningless! Space that isn't connected shouldn't be part of the same tree on *any* level!
This means starting with splitting the map into cubes of geographic areas, and then looking to make sure that all nodes in those cubes connect with one another, and splitting of any cubes which do not have connectivity. You then stitch together trees out of the nodes that are still in those geographic areas have connectivity, and then you build the next level of hierarchy as a way to get from one geographic area to the others.
You have to divvy space up on the basis of choke points, or maximum convex regions or some other heuristic. Which one though?
Of course they aren't part of the same tree if they aren't connected.
This isn't a problem at all - if you cannot find a connection for some reason, you just start building another tree. Only connected nodes are connected to the same tree. Connection on a tree IS the implication of connectivity on the map, after all.
QuoteThe other option is that you can start from an arbitrary point somewhere in the "middle" of the map:Could you draw a picture of that? *scratches head* Does every subtree become a single node in the L2 tree or multiple nodes? If multiple, how is the L1 tree subdivided to make L2 nodes?
This works best with the innate nature of a tree data structure, upon further thought, since it relies upon some of its basic principles, and assumes some dynamic ability to shift to changing nodes.
Pick a node, any random node on the map.
Now, you have to start connecting all its adjacent nodes to it as branches, and start building a tree.
During this process, the tree needs to "balance" itself, which is a basic function of many trees. This means that the "root node" will change to be the node with the most roughly-equidistant leaf nodes hanging off of it. (This means that you don't want a lopsided tree, if a branch becomes larger than the rest of the tree, the start of that branch becomes the new root, and the old root becomes a branch of the new root.)
Once you hit a certain point of complexity, say ten tiers on the tree structure, it is time to build the next level of hierarchy. In this, the root node becomes not only a root node for the level-1 tree that we were building before, but also the root node of the level-2 tree, which acts as the geographical equivalent of moving from a city-level to a state-level of travel. Each of those other level-1 trees becomes filled out with new root nodes for their level-1 trees, based upon the fastest connection to the root node of the level-2 tree. Each of these new level-1 trees is now a branch of the level-2 tree. You then keep on going, populating the level-1 trees until they have to simply split off, and make a new level-1 tree which they are connected to.
That doesn't really answer my question. How do you create that tree from a L1 tree? Could you draw the original next to it? Because, I'll be frank, it seems to me that you've missed some logical steps. Why didn't all the children of the original root node become L2 nodes, but only 3 of them?Spoiler: large image (click to show/hide)
Anyway, it's not that much more complex than a regular tree - instead of a tree node containing a single map node's data, it contains a link to another tree (the red lines). It's just using a minor bit of recursion in the data structure.
If you understand trees at all, it's just a fairly simple extension of the concept.
I was talking about only the tree-based pathfinding here, without also imposing the hierarchical scheme you suggested subsequently. If all you have are cities, not states or any larger groups, you'll still have the problem I describe. Just clarifying.
No, you misunderstand. I really meant passing-through. If St. Louis has only, say, 10 major entry points you need to store 45 costs. All well and good. But what about the state of Missouri? It will likely have hundreds of entry points, meaning thousands of costs to pre-compute and store.
I'll reiterate my main point: Hierarchical representations only help you if the world conforms to that hierarchy. Cities are natural clusters as far as pathfinding is concerned -states are not. Nor, as I said, are any Dwarf Fortress subdivisions except for "room" that I've heard proposed.
Star shaped topologies help you only if the world is star-shaped.
Quad trees help you only if the world has large square chunks of free space/occupied space. And if you impose a quad tree over a DF map, you're going to have an entry point count that is proportional to the length of the sides, meaning O(L^2) costs to be precomputed.
Basically: No free lunch. The only way to beat unbiased tile-by-tile BFS is to bias the search. A* biases in favor of worlds with straight-ish paths. Room-based nodes bias in favor of worlds which actually have rooms. Your tree search approach biases (heavily) in favor of worlds with a star-shaped topology. Your hierarchical search biases in favor of worlds with scale invariance.
Nothing wrong with any of this - one just have to go into it with open eyes. It happens to be my belief that both the star-shaped world assumption and the scale invariance assumption will be quite off in many, if not most Dwarf Fortress maps.
I'm going to break off answering this into discrete chunks at this point...Good, we're on the level then. I just wanted it clear for the record that, on its own, the tree pathfinding though fast won't produce optimal paths (unless the map is star-shaped). Which is why you propose modifications/additions to it, to smooth that bias out. Nothing wrong with that.I was talking about only the tree-based pathfinding here, without also imposing the hierarchical scheme you suggested subsequently. If all you have are cities, not states or any larger groups, you'll still have the problem I describe. Just clarifying.
Well, the thing is that the tree-based pathfinding is optimized for finding a path with the least amount of processor time consumed possible.
It is NOT trying to find the optimal path for a dwarf to get from point A to point B in the shortest number of steps. It IS trying to make the processing-time-optimal calculation to find ANY valid path.
You are complaining that the form of the function that isn't concerned at all with distance optimization isn't distance optimized. Of course it isn't - it's not even supposed to be!
It's only the alternate versions, where we aren't optimizing one over the other that you have something closer to distance-optimization. But it's still a tradeoff.
It's like seeing a boat, and complaining about how it's really hard to handle on the Interstate. It wasn't ever built to accomplish that function in the first place.
I'm not misunderstanding, this is exactly what I was talking about.OK, sorry if I misunderstood; it looked like you were talking about within-unit pathing.
Missouri might have 100 entry points, but you don't need to actually record all of them. That's what I said about recording only the best of them.
Missouri is only connected to, what, 5, 6 different states? All you need to record is the best path if you are traveling through Missouri from one state to another. Typically, this means you just stay on the Interstate the whole way through.
That's a pretty uncharitable thing to say. I've said that the "shortcut" solution you suggested won't cut it unless you can show how it is combined with your hierarchical scheme, and to my mind you haven't yet. That's not "not paying attention".I'll reiterate my main point: Hierarchical representations only help you if the world conforms to that hierarchy. Cities are natural clusters as far as pathfinding is concerned -states are not. Nor, as I said, are any Dwarf Fortress subdivisions except for "room" that I've heard proposed.
Star shaped topologies help you only if the world is star-shaped.
Quad trees help you only if the world has large square chunks of free space/occupied space. And if you impose a quad tree over a DF map, you're going to have an entry point count that is proportional to the length of the sides, meaning O(L^2) costs to be precomputed.
Basically: No free lunch. The only way to beat unbiased tile-by-tile BFS is to bias the search. A* biases in favor of worlds with straight-ish paths. Room-based nodes bias in favor of worlds which actually have rooms. Your tree search approach biases (heavily) in favor of worlds with a star-shaped topology. Your hierarchical search biases in favor of worlds with scale invariance.
Nothing wrong with any of this - one just have to go into it with open eyes. It happens to be my belief that both the star-shaped world assumption and the scale invariance assumption will be quite off in many, if not most Dwarf Fortress maps.
But this is, again, completely ignoring some of the solutions to these exact problems I've already outlined.
If you want to optimize for direct paths, you have to use a method which trades performance in terms of processor power and memory storage in exchange for better distance pathfinding optimization.
I've already discussed different gradients of ways to do this - duplicate-information storage in the tree WILL enable trees to become less "star-shaped" by having the "star" overlap on top of itself.
This is specifically HOW to avoid the "going to St. Louis to get to Pasadena" problem you were talking about - but you don't seem to be paying it any attention at all.
But this is not a solution if you think about it.
What's the "best" path from Arkansas through Missouri to Kansas? Looking at Google Maps, it looks like that's Bella Vista to Galena - about 25 miles.
What's the "best" path from Tennessee through Arkansas to Missouri? Crossing at Blytheville you can do it in 20 miles.
So - this proves you can get from Tennessee to Kansas in less than 50 miles. Or? I'm not being facetious here - try it yourself. If you had some other definition of "best" path in mind, what is it?
You can smooth things out later by doing regular intranode pathfinding at each node along the way. If the nodes make sense, this should be a larger quantity of very cheap calculations relative to what the game does now, and the cheapness should more than make up for the larger quantity.
That's a pretty uncharitable thing to say. I've said that the "shortcut" solution you suggested won't cut it unless you can show how it is combined with your hierarchical scheme, and to my mind you haven't yet. That's not "not paying attention".
So why do a tree, as opposed to just A* on the nodes? It seems like A* on nodes would be fast enough in and of itself, and would be easier to implement. I mean, I think the tree is a great idea and I don't see any problems with it, but does it have any advantages other than a little more speed? Or would it really be that much faster?
You can smooth things out later by doing regular intranode pathfinding at each node along the way. If the nodes make sense, this should be a larger quantity of very cheap calculations relative to what the game does now, and the cheapness should more than make up for the larger quantity.
Okay, so here's a question. It's obvious that you have to split the map up into nodes larger than a single space in order to improve the pathfinding. You can't really improve upon A*, so you trade space for time.
So the map's split up using some elegant node-choosing algorithm. This alone is going to speed up pathfinding considerably. When I try to get out of a building when I'm on the third floor, I don't first try and go through the floor below me, then search for an alternate path. I path to the door, then I path to the stairs, then I path down to the first floor, then I path to the exit.
So why do a tree, as opposed to just A* on the nodes? It seems like A* on nodes would be fast enough in and of itself, and would be easier to implement. I mean, I think the tree is a great idea and I don't see any problems with it, but does it have any advantages other than a little more speed? Or would it really be that much faster?
I'm curious about what would happen with wide-open spaces, though. What about outside the fort? Is the whole exterior going to be one node, or will it be sliced up into smaller blocks? If you slice it up, then you have a lot of pieces connecting to each other, and that doesn't much fit into a tree. You can arbitrarily assign a top node and then file things away, sure, but you'll end up in situations where the paths are extremely suboptimal.
In terms of the US map, you're going from AZ to WY, and the root node is OK, so you pick out a path AZ->NM->OK->KS->NE->WY. That's six steps from something you could do in two. You can't find a shortcut since there's no direct path between any of the nodes you're going through. I know the goal isn't to find an optimal path, but take this a few steps further out (Florida to Maine?) and you end up with paths that aren't even good. A slightly meandering path is one thing, but your dwarves could easily end up prioritizing a point in the middle of nowhere that has no real significance to your fort.
It seems like the best thing to do here would just be to make the entire outside area one single node, or a few very very large nodes. That way the high-level nodes would be a lot more likely to end up in the right places, and you wouldn't have a faux-tree of nodes that are all really connected to each other. But doing that makes it hard for me to wrap my head around how you would go about splitting up the map into nodes in the first place.
You've probably considered/discussed this already, so apologies if I'm rehashing things you've already been over.
o........o........o........o........o........o
. .
. .
. .
o o
. .
. .
. .
o o
. .
. .
. .
o........o........o........o........o........oo........o........o........o........o........o........o........o........o........o........o
. . .
. . .
. . .
o o o
. . .
. . .
. . .
o o o
. . .
. . .
. . .
o........o........o........o........o........o........o........o........o........o........o2D simulation
...,................................................................................................
. .
o........o........o........o........o........o........o........o........o........o........o........o
. . . .
. . . .
. . . .
o o o o
. . . .
. . . .
. . . .
o o o o
. . . .
. . . .
. . . .
o........o........o........o........o........o........o........o........o........o........o........o
. .
...,................................................................................................
You can't really improve upon A*You totally can if you use more specific heuristics. A* is a very good general-case solution for a totally random graph, but if you know some general features of the graph beforehand, you can use heuristics customized to the case you're dealing with to speed up pathfinding, sometimes immensely.
More specific heuristics?I must say that I remain a bit wary about "Well, we know there'll be corridors and rooms..." coming into discussions about how to make a better A*, or why to swap to a 'better'-than-A*-when-it-comes-to-corridors-and-rooms system.
*Doing the pathcheck to the impassible-to-dig tile does save CPU, yes, but the point remains: we're not trying to find the best path we're trying to find a reasonably short route quickly.
2. The algorithm values the Z axis less than the horizontal axis. Optimized for ramp seeking greed, the A* algorithm searches every Z levels (between the origin and the target) in hope of finding a ramp. Incredibly stupid 'optimization' for the sake of trivial outdoor pathfinding. Sane DF heuristic should value underground Z levels as a top priority. Stairs/Ramps are relatively rare, and should be highly valued when they are found.
- DF A* pathfinding algorithm should use non-taxicab heuristic horizontally, but not vertically. Ex.: max(abs(x1-x2), abs(y1-y2)) + abs(z1-z2)
- Optionally, outdoor heuristics should also have an option (on by default) to also use non-taxicab vertically, for the sake of the outdoor ramp layout. Ex.: max(abs(x1-x2), abs(y1-y2), abs(z1-z2))
Fixing A* worse case scenarios will require a solution like implementing a node system engineered around vertical access points. I repeat, tweaking A* will not fix anything.
2. The algorithm values the Z axis less than the horizontal axis. Optimized for ramp seeking greed, the A* algorithm searches every Z levels (between the origin and the target) in hope of finding a ramp. Incredibly stupid 'optimization' for the sake of trivial outdoor pathfinding. Sane DF heuristic should value underground Z levels as a top priority. Stairs/Ramps are relatively rare, and should be highly valued when they are found.
- DF A* pathfinding algorithm should use non-taxicab heuristic horizontally, but not vertically. Ex.: max(abs(x1-x2), abs(y1-y2)) + abs(z1-z2)
- Optionally, outdoor heuristics should also have an option (on by default) to also use non-taxicab vertically, for the sake of the outdoor ramp layout. Ex.: max(abs(x1-x2), abs(y1-y2), abs(z1-z2))
I'm sorry, but what, exactly, is the reasoning behind this?
I can assure you that stairwells are anything but rare in many fortresses, and not all fortresses by any means use a "Central Stairway" approach to construction.
Because, I'm being pragmatic.Fixing A* worse case scenarios will require a solution like implementing a node system engineered around vertical access points. I repeat, tweaking A* will not fix anything.
Yes, well, that's sort of what's been said throughout the thread on everything but the first proposals sockless made, excepting the "engineered around vertical access points" part, since you can't assume that vertical access points mean anything.
Every single fortress use the central stairway approach, it's just that some have more than others.
Why?
Because, literally, you can't build on vertical movement tiles, while even vertical movement tiles are horizontal movement tile, .
So, literally, all fortresses need to build their stuff next/away from vertical access tile, and the majority of that 'stuff' will not block horizontal movement.
Unless you want to build a fortress that specificaly designed to be a maze, your fortress will be much easier to navigate horizontally than it will be vertically.
Because, I'm being pragmatic.
Any node system needs nodes.
There's no reason a node system would need to replace A*, supplementing it is far wiser.
If DF uses both a node system and a A*, it would be stupid to optimize the node system to solve the pathfinding problems that A* is already able to solve efficiently.
What A* can't handle efficiently are large/complex obstacles. 3D maps can increase both the size & complexity of obstacles exponentially.
Hence the worst case scenarios for A* will invariably involve Z levels, which requires vertical access points.
So by using vertical access points as nodes, you end up using the node system when and where you usually need it the most.
But sure, you can try to design an algorithm to find navigation nodes in a complex 3D maze of rooms, that could be more effective at pathfinding.
But see how designing that system goes for you and how much Toady cares about the 'solution'.
1. The heuristic estimate is of 1 per tile, not 2 per tile as it should be. That incurs an ridiculously huge performance penalty (1000x the cost or more in common otherwise optimal A* scenarios) for the sake of naive traffic cost agendas.
2. The algorithm values the Z axis less than the horizontal axis. Optimized for ramp seeking greed, the A* algorithm searches every Z levels (between the origin and the target) in hope of finding a ramp. Incredibly stupid 'optimization' for the sake of trivial outdoor pathfinding. Sane DF heuristic should value underground Z levels as a top priority. Stairs/Ramps are relatively rare, and should be highly valued when they are found.
3. The system uses taxicab heuristics, but non-taxicab movement costs. Wtf really.
- Optionally, outdoor heuristics should also have an option (on by default) to also use non-taxicab vertically, for the sake of the outdoor ramp layout. Ex.: max(abs(x1-x2), abs(y1-y2), abs(z1-z2))
Any node system needs nodes.
There's no reason a node system would need to replace A*, supplementing it is far wiser.
If DF uses both a node system and a A*, it would be stupid to optimize the node system to solve the pathfinding problems that A* is already able to solve efficiently.
What A* can't handle efficiently are large/complex obstacles. 3D maps can increase both the size & complexity of obstacles exponentially.
Hence the worst case scenarios for A* will invariably involve Z levels, which requires vertical access points.
So by using vertical access points as nodes, you end up using the node system when and where you usually need it the most.
But see how designing that system goes for you and how much Toady cares about the 'solution'.
Every single fortress use the central stairway approach, it's just that some have more than others.
Why?
Because, literally, you can't build on vertical movement tiles, while even vertical movement tiles are horizontal movement tile, .
So, literally, all fortresses need to build their stuff next/away from vertical access tile, and the majority of that 'stuff' will not block horizontal movement.
Unless you want to build a fortress that specificaly designed to be a maze, your fortress will be much easier to navigate horizontally than it will be vertically.
This is how I build workshops, so as to be efficient, and control what stones are selected for products.Spoiler (click to show/hide)
No matter how much I dig downward, I am only moving my workshops 1 step further away from the stockpile per 6 workshops I build.
I also have a layer of pure soil between the stockpile layer and workshops because I want to preserve the chance to have underground trees, so you can generally assume that trip is more vertical than horizontal.
Generally speaking, I just segregate my fortress horizontally, and then do my "sprawl" vertically, preferring narrow, yet deep fortresses.
That's just building for a particular form of optimization, however. I wasn't feeling artsy when I was doing that, except to make a hexagon instead of a square, and just made it compact and efficient. If we want to go for a truly extreme version, we can go look at
Undergrotto (http://www.bay12forums.com/smf/index.php?topic=50916.0) once again.
No, as I explained, it is you that does not understand that the game has a concept called 'floors', which is not present on the horizontal version as walls need a whole tile. Those 'floors' are everywhere under and over your workshops and rooms, and they are a serious impairment to pathfinding.Because, I'm being pragmatic.
Any node system needs nodes.
There's no reason a node system would need to replace A*, supplementing it is far wiser.
If DF uses both a node system and a A*, it would be stupid to optimize the node system to solve the pathfinding problems that A* is already able to solve efficiently.
What A* can't handle efficiently are large/complex obstacles. 3D maps can increase both the size & complexity of obstacles exponentially.
Hence the worst case scenarios for A* will invariably involve Z levels, which requires vertical access points.
So by using vertical access points as nodes, you end up using the node system when and where you usually need it the most.
But sure, you can try to design an algorithm to find navigation nodes in a complex 3D maze of rooms, that could be more effective at pathfinding.
But see how designing that system goes for you and how much Toady cares about the 'solution'.
Actually, there's little reason that a nodal system would really need to see a difference between a horizontal "hallway" and a vertical "hallway" made of stairs. They theoretically cover the same distance, and dwarves move through them equally. You're creating artificial barriers to how you generate nodes simply because of your mindset of how z-levels work.
In fact, since any revised node system should be capable of including proper pathfinding for flying creatures and swimming creatures, the assumption that all creatures will be pathing to points along a flat surface is simply not one you can make - you need to build cubic nodes if you want to allow for a proper swimmer or flier pathing system.
The difference between building a "square" and a "cube" based nodal system is trivial, as has been discussed at length in this thread.
Further, using a node-based system, as I already said, is something everyone agrees to immediately. The point of contention is how to form and adjust and split those nodes, and how best to organize those nodes.
That has nothing to do with Manhattan vs Diagonal heuristic.1. The heuristic estimate is of 1 per tile, not 2 per tile as it should be. That incurs an ridiculously huge performance penalty (1000x the cost or more in common otherwise optimal A* scenarios) for the sake of naive traffic cost agendas.
Unless you meant using FP instead of integer values and sqrt(2) for diagonal travel, I really don't see your point here. If you stay with integers, the only possible penalty is a (slightly) higher chance of reaching the point of sign overflow - with higher edge traversal costs nonetheless, not smaller.
I don't think you can really solve that problem with heuristics alone, even though I agree that your suggestion might help a little.
if you want I can fix my simulator to double the hueristic but I don't think it would help much. A* likes getting lost and it easily get confused by hueristic. my approach for solving the complexity is by reducing the distance, and saving common pathes.Combined reply.
...[beautiful Phoebus-diagrams :D]...
This is exactly my point. No amount of A* tweaking is ever going come even close to solve DF's pathfinding problems.
But that's the problem, A* is already heavily tweaked in attempt to solve DF's pathfinding problems.
It's tweaked so bad that even if a good node system is implemented in DF, the cost of using current A* to pathfind between nodes is still going to make the whole pathfinding process cost 2 to 5 time more processing power than it should.
I'm proposing to un-tweak the A* engine back to the actual standard way in which it's supposed to work.
I don't think I was ever arguing admissible (optimal final result) heuristics....[beautiful Phoebus-diagrams :D]...
You are talking about admissible vs. inadmissible heuristics. General rule: having the heuristic overshoot the cost = admissible, meaning guaranteed shortest path. Underestimation = inadmissible, meaning you get a path, but not a guaranteed shortest, and possibly with an open list like your example. OK; I see what you mean. Just... How did you come to the conclusion that DF uses inadmissible h(x)?
I can only agree with DF needing search algorithms that scale better.This is exactly my point. No amount of A* tweaking is ever going come even close to solve DF's pathfinding problems.
But that's the problem, A* is already heavily tweaked in attempt to solve DF's pathfinding problems.
It's tweaked so bad that even if a good node system is implemented in DF, the cost of using current A* to pathfind between nodes is still going to make the whole pathfinding process cost 2 to 5 time more processing power than it should.
I'm proposing to un-tweak the A* engine back to the actual standard way in which it's supposed to work.
I'm still heavily convinced that PF isn't the real problem in DF, and that a hierarchic search would even pretty much solve the worst case of 'no path exists' - because it would come to the same conclusion in a fraction of the effort it needs in a flat structure. It would be equivalent to having a cut-off depth in the current version equivalent to the number of nodes in the current strongly connected component (http://en.wikipedia.org/wiki/Strongly_connected_graph) of the high level graph.
But the game can currently be inadmissible when you consider the misuses of Manhattan heuristics in a game with diagonal movement. Optimal paths can be missed by the engine due to that.
Heuristics for diagonals and ramps = 2. Heuristics for diagonal ramps = 3. Movement cost (High Traffic) for those is 1.
But, are optimal paths really that necessary?
I can only agree with DF needing search algorithms that scale better.
No, as I explained, it is you that does not understand that the game has a concept called 'floors', which is not present on the horizontal version as walls need a whole tile. Those 'floors' are everywhere under and over your workshops and rooms, and they are a serious impairment to pathfinding.
If floors did not exist, if dwarves could fly and if buildings could float, then your argument would be valid, but it is not so.
Floors/Z-levels are the primary pathfinding obstacle in the game. By far.
Those missed paths could be optimal, movement cost wise, if it managed to connect with a direct path of High traffic (1 cost) tiles to the destination. Very uncommon, and suboptimal step wise.But the game can currently be inadmissible when you consider the misuses of Manhattan heuristics in a game with diagonal movement. Optimal paths can be missed by the engine due to that.
True, diagonal movement needs both cost and heuristic of ~sqrt(2) (can be simplified to 1.4, or even lateral 5 / diagonal 7 if you want to keep integer math), else your diagram happens.
Thinking out loud though... Is that missed path even a non-optimal one, if movement costs the same in every direction? Sure, it may look idiotic if the dwarf walks straight-line NE first, then straight SE, only to arrive on the same y-coordinate as he started from. But if it takes him the same time and number of steps... ? (The path, not the search!)
I did a few tunnels with levers, I calculated the heuristic values that way.Heuristics for diagonals and ramps = 2. Heuristics for diagonal ramps = 3. Movement cost (High Traffic) for those is 1.
Did you experiment with the traffic costs? I'd be interested in the !science!.
I agree with the sentiment about dwarves needing to think.But, are optimal paths really that necessary?
Not in my humble opinion... (http://www.bay12forums.com/smf/index.php?topic=64580.msg1515644#msg1515644)
QuoteI can only agree with DF needing search algorithms that scale better.
Especially for history, material and item lists.
Must the game only use a single pathfinding algorithm for all creatures?No, as I explained, it is you that does not understand that the game has a concept called 'floors', which is not present on the horizontal version as walls need a whole tile. Those 'floors' are everywhere under and over your workshops and rooms, and they are a serious impairment to pathfinding.
If floors did not exist, if dwarves could fly and if buildings could float, then your argument would be valid, but it is not so.
Floors/Z-levels are the primary pathfinding obstacle in the game. By far.
No, as I explained, this needs to be capable of handling flying and swimming creatures, and there is no real benefit to having a pathfinding structure that penalizes vertical travel and makes the game incapable of pathfinding for two modes of travel for a minor optimization under a certain set of circumstances that you are just assuming will be more common.
The gains you are making are trivial, and the costs are serious. It's just not worth it.
Combined reply.
This is exactly my point. No amount of A* tweaking is ever going come even close to solve DF's pathfinding problems.
But that's the problem, A* is already heavily tweaked in attempt to solve DF's pathfinding problems.
It's tweaked so bad that even if a good node system is implemented in DF, the cost of using current A* to pathfind between nodes is still going to make the whole pathfinding process cost 2 to 5 time more processing power than it should.
I'm proposing to un-tweak the A* engine back to the actual standard way in which it's supposed to work.
The complexity is about min((k/2)^N ,Nmax) which means node explosion . A* is also fooled by dead ends . there are a few examples for this
one thing i have noticed about the A* approach (and probably most others) is the exponential increase in calculations over greater distance (due to the exponential increase in path options, most of which are redundant and unnecessary)
there are two suggestions i have. one would help a lot for pathing in a fortress. by breaking the fortress down into rooms separated by doors, you could simplify the code by using a macroscopic version to calculate what rooms you need to go to, and a microscopic one for pathing through each room. even if it needs to preform the same amount of pathing checks it won't have to do them all at once, only once every time the object enters the room, spreading the lag more evenly. this also means numerous shorter distances instead of one long one minimizing the exponential growth in possibilities ( i know it is better then exponential but the algorithm hates distance. you could even use memory to store the path from one end of the room to the other (though this would have to be compiled and called on when needed because RAM is taxed as it is (i think))I think that's around page 15-17 or so of this thread.
Must the game only use a single pathfinding algorithm for all creatures?No, as I explained, it is you that does not understand that the game has a concept called 'floors', which is not present on the horizontal version as walls need a whole tile. Those 'floors' are everywhere under and over your workshops and rooms, and they are a serious impairment to pathfinding.
If floors did not exist, if dwarves could fly and if buildings could float, then your argument would be valid, but it is not so.
Floors/Z-levels are the primary pathfinding obstacle in the game. By far.
No, as I explained, this needs to be capable of handling flying and swimming creatures, and there is no real benefit to having a pathfinding structure that penalizes vertical travel and makes the game incapable of pathfinding for two modes of travel for a minor optimization under a certain set of circumstances that you are just assuming will be more common.
The gains you are making are trivial, and the costs are serious. It's just not worth it.
(That's a rhetorical question.)
This is the whole point around my argument. The current pathfinding algorithm has been broken to solve problems that it can't really solve. As you put it, serious costs for trivial gains.
The goal of fixing A* is not to fix the pathfinding problem (which it can't), the goal of fixing A* is to have a A* that does it's job, and then let other solutions take care of what A* can't handle.
A solution example that would improve things without breaking A* wouble be to have a different A* heuristics for creatures with different mode of travel.
This is not even some mind-blowing idea, that's just how heuristics are supposed to work.
It's also the reason why I proposed configurable A* settings options, because different fort design have different pathfinding expectancies. While those options will have minor benefits, they are also cheap to implement and have no actual costs as they are options.
I did a few tunnels with levers, I calculated the heuristic values that way.
One of my first test that left me puzzled was an obstacle course with tunnels.Strangely enough, the dwarves usually prefer to move through the underground tunnels. The tunnels have exact same traffic settings as overground tiles.Spoiler (click to show/hide)
Somehow the dwarves prefer the path that's moving away both horizontally and vertically from the destination.
That only made some kind of sense after I figured the path cost debt caused by the D = 1 heuristic vs. 2 cost normal traffic. Even then that behavior is, even if explainable, still somewhat abnormal as the overland cost should be traced first. It's possible the engine is actually pathfinding several times over the same time (if the second pass has equal or better heuristic estimate), or at least overwriting early tracebacks with later ones of equal travel cost.
Those missed paths could be optimal, movement cost wise, if it managed to connect with a direct path of High traffic (1 cost) tiles to the destination. Very uncommon, and suboptimal step wise.I'd also have to say that what you are really harping over - the traffic costs - is something that actually has a very simple fix. Either do what the system was meant for you to do, and set all your hallways to be high-traffic zones, which nobody really does, and hence proves this a broken system, or go into the init options, and set standard traffic weighting to be 1.
the other method is a modified A* (don't kill me) i have a Wikipedia understanding of A* (meaning i looked at the Wikipedia animation) using the animation as an example, the program traces a line towards it's target. the line hits the wall, and instead of expanding from there, it follows the wall in both directions until one becomes free to move again. the program then begins to trace between these points, and if it collides again it repeats this task. then, after it arrives, it begins to continue it's course. i might create an example when im not exhausted and can think.That algorithm isn't applicable to DF because the heuristic is optimized for 2D. In DF there can be stairways/ramps in the middle of the room and that modified A* would just walk around them/ignore them.
These pointless threads come up all the time, kind of ignoring the fact that Toady knows math hehe.
I'm almost tempted to write a hack that lets you guys plug your own pathfinders into DF just so you can see how pointless your ideas are... it wouldn't be that hard...
:-\ I don't think I'll take any part of *that* . I'm here to suggest stuff not to "fix" the code through hacks. Controlling the game with external apps is one thing, changing the game engine is borderline copyright infringement ~ .These pointless threads come up all the time, kind of ignoring the fact that Toady knows math hehe.
I'm almost tempted to write a hack that lets you guys plug your own pathfinders into DF just so you can see how pointless your ideas are... it wouldn't be that hard...
Now *that* would be an interesting mod.
:-\ I don't think I'll take any part of *that* . I'm here to suggest stuff not to "fix" the code through hacks. Controlling the game with external apps is one thing, changing the game engine is borderline copyright infringement ~ .
I'm not sure why devek is so resistant to any path-finding related suggestions. He might be right that path finding improvements would be a waste of time because it might not take as many CPU resources as we think. My limited test didn't suggest memory thrashing .
It still seems logical that path finding improvements would lead to FPS improvement because that what all creatures do most of the time.
You hit the nail on the head. Before Toady did DF, he was paid money to know math. It is kind of like going up to a race care driver and telling them they could take faster turns if they focused out for their weight distribution, it is kind of pretentious.
You hit the nail on the head. Before Toady did DF, he was paid money to know math. It is kind of like going up to a race care driver and telling them they could take faster turns if they focused out for their weight distribution, it is kind of pretentious.I'm not sure what Toady's background but if someone wants to suggest a better pathfinding algorithm they better know something in the field of computer science, discrete mathematics etc and be able to offer code or well outlined implementation.
Don't get me wrong though, there is nothing wrong with pathfinding improvements. It would be nice if when a dwarf constructed a wall, that it did it from the closest tile instead of always building from one side, it would be nice if it grabbed the stone that was close or on the way, it would be nice if we had multi-tile monsters, etc. Toady isn't sitting around trying to figure out how to do it, he is simply busy working on other things(like hill dwarfs, taverns, and cities!). We will get those things when they get to the top of the enormous list of things left to do.The issue with dwarfs always building from top can easily solved with some weighing and heuristics I don't think that it's such a major issue anyways. Just open the circus if you want FPS to drop ;) and there aren't that many clowns in there but they certainly kill fps in their marketing campaign . they got big k and big N to reach their customers and they can reach more nodes than anyone else.
It is also logical that you could improve FPS by improving any piece of code, but premature optimization is a killer waste of time. The truth is, exponential slowdowns in DF are the result of bugs. The most useful thing the user can do is upload saves before and after such slowdowns occur. Furthermore it is difficult sometimes figuring out how to properly write a piece of code when you don't know what it is going to do, DF is a huge work in progress.
For example, let me show you a graphed view of the function that determines what an object is when you look at it.Spoiler (click to show/hide)
There is so much waste in that I could cut away with a few key strokes, but why bother? Right now it is flexible enough to add all sorts of cool new features and items to the game. The biggest performance gains are not possible to implement until you actually know what you are trying to do.
I'm not sure what Toady's background but if someone wants to suggest a better pathfinding algorithm they better know something in the field of computer science, discrete mathematics etc and be able to offer code or well outlined implementation.
That looks like a call stack or something - look kinda blurry. I admit I have no Idea what's killing my CPU. If it's the dwarfs looking for items, thiefs looking for stuff to steal or 200 cats looking for who know what. All I know is that more Mobs = less fps which probably translate to pathfinding. I know that turning off temperatures boosts FPS I haven't checked fluids flow. Maybe its the magma?!
This is why I like path finding optimization approach and you don't really have to add much . It's a classic divide and conquer approach that every CS major should knows by heart .
I do agree that profiling would get us far but I got no clue how to do it on someone else's code on a windows platform.
If "just wait until Toady gets around to it" isn't enough for people, then a real investigation into pathfinding should start with trying to reproduce the existing DF pathfinding on actual maps (via dfhack) and establish plausible test scenarios that demonstrate the slowdowns observed in real games. You can't make any progress on a solution until you know what problem you're trying to solve.
Learning and applying this stuff is a good thing. Sadly, most colleges don't teach up to date programming techniques :/ CPUs today are fast, like REALLY fast but memory isn't very fast. When you get it, you'll understand why it is just as expensive to path up one z-level as it is to path out 16 tiles horizontally. Check out this pdf from Sony for example...Being an embedded programmer I know this kind of stuff. I can tell you a thing or two about udp packet transmission and the downfalls of classic network stacks ::) . I am a big supporter of "link list = caching disaster" . I once improved udp transmission from 200us to 20us ;D.
http://research.scee.net/files/presentations/gcapaustralia09/Pitfalls_of_Object_Oriented_Programming_GCAP_09.pdf
It takes a common programming case and improves its performance from 20ms to 3ms with simple reorganization. The case is very similar to a lot of processing DF does :)
Designations are a separate 16x16 array per mapblock from the pathfinding data, they are for... designations like digging or channeling and such :) If it was up to me, that data would be replaced with a designation list but whatever hehe.
This has been done, however.
...
As Phoebus was recently pointing out, the game prefers to look for ramps over looking for stairs.
...
Likewise, there have been threads which detail testing of how the A* is set up, and how the pseudo-ideal fort shape is a giant cube of up/down stairs that has no walls whatsoever, and allows dwarves to pathfind freely through space.
The reason why pathfinding takes up so much processor time is because the game needs to randomly access very large amounts of memory in nonsequential (functionally random) order, meaning that the typical pipelining performance boosts generally just burn processor power for no gain.
Designations are a separate 16x16 array per mapblock from the pathfinding data, they are for... designations like digging or channeling and such :) If it was up to me, that data would be replaced with a designation list but whatever hehe.
Right here I mean, it looks like traffic is stored as part of the designation data: https://github.com/peterix/dfhack/blob/master/library/include/dfhack/modules/Maps.h#L300
Or maybe I'm misreading.
Because something like this:The reason why pathfinding takes up so much processor time is because the game needs to randomly access very large amounts of memory in nonsequential (functionally random) order, meaning that the typical pipelining performance boosts generally just burn processor power for no gain.
is an entirely empirical question and can't just be assumed.
This is generally why I look at node accesses as my benchmark . everytime you go through a node you don't know what kind of disastrous memory fetches you'll get unless the map is a very small bit vector. just to think that you have to go to check the weights too. Who know what other useless data you are gonna fetch along with it.
CPUs today are fast, like REALLY fast but memory isn't very fast.
| a*-max(draw) | room-min(draw) | a* | room | redraw |
| 139 | 7 | 184 | 37 | 40 |
| 85 | 19 | 130 | 49 | 33 |
| 86 | 9 | 131 | 39 | 45 |
| 96 | 12 | 141 | 42 | 30 |
| 97 | 11 | 142 | 41 | 38 |
It's not assumed, it's known that searching very large vector matrices thousands of times takes a lot of memory fetches.
So, not being totaly up to date on processor designs, is the time spent waiting on a memory fetch nearly completely idle on modern CPU's? or do other threads whos code/data are in cache get a chance to run? (and only 'hardware' threads, like Intel's 'Hyperthreading', or OS level threads/processes?
I'd love to see some benchmark results for DF on otherwise indentical CPU's except for L1 cache size.
It's not assumed, it's known that searching very large vector matrices thousands of times takes a lot of memory fetches.
That part is known. The assumption is that that phenomenon is the main factor determining the performance of the current pathfinding algorithm.
EDIT: Or maybe "hypothesis" is a better word. It's based on reasonable assumptions, and fits previous observations, but has yet to be tested against alternative hypotheses.
Well, if we are agreeing that memory fetch time is a bottleneck, but not that it is the bottleneck, then what it comes down to is if there is something out there that is an even worse bottleneck that causes the CPU to burn tremendous numbers of cycles trying to calculate something when the math is actually fairly simple for a computer.
Creating nodes(waypoints) over 2d space is pretty trivial, but you have to do it in 3d space.doing this in 3d space is trivial it's also not that necessary because you can keep 2d space per level and keep looking per z level . It might be a lot of memory but it's not too bad. I can convert my simulator to work in 3d but the transitions between Z levels would need a modification to alow it to know if there are "stairs" or something like that in the node.
Once you're done, you might as well be generating vectors. With a mesh you can do things like create monsters that take up more than one tile. Imagine a dragon that can't get in your fort because it is too tall. Imagine siege engines that can shoot downwards.The width can be handled easily by saving multiple access points and their width. I'm not sure A* can handle width anyways.
Imagine a dwarf grabbing a nearby stone instead of crossing the entire map.Nearby stone is simplified by this algorithm because if you need to find a path for each stone you will pay a smaller penalty for unreachable objects.
I brought this up once but you shot it down because it had to be generated and changed each time the map was modified, now that is exactly what you're talking about :P
Well, its true you don't have to totally regenerate with any system. When someone digs out a room you just add to the nodes/mesh either way and optimizing it during spare cpu time.I don't think it would hang for a second. With a non-caching method all you need to keep track of is weather a "room" is accessible or not. You should also consider the fact that the UI and user are significantly slower than the back-end and CPU. When you make a change you might want to go through path validation but that's pretty quick on room paths(no guesswork either), or let everyone hit the wall(like they do now.
What sucks (for any method)is when someone locks a door, currently you can feel DF hang for a second recalculating its pathfinding data.
Either way, your method will work and it is going in the right direction now. With a mesh or nodes, you're actually working with a proper graph now and this is where things actually improve. Feel free to burn as much cpu building/maintining your graph, in the end it is cheaper than traversing a suboptimal one.
I don't think it would hang for a second. With a non-caching method all you need to keep track of is weather a "room" is accessible or not.
It's not a matter of "proper" or not the current map is fine as a graph the problem is that it's really big and too complicated. I've read in a book google scaned that they don't recommend using pure A* on "boards" larger than 60X60. What DF has in a 4X4 embark is a graph 192X192X100 ::) or 3.7~ million nodes.
The more you get into this, you will see why I hate people that are like, "derp, use this pathfinding function instead derp!" but you are clearly not one of those people now since you're analyzing the dataset so I like you now. <3
Even putting the data in contiguous memory would have a bigger impact on performance than any other change you could possibly make in the pathfinding code itself. Right now to simply access a single tile, you have to dereference 5 pointers to get there. array->X->Y->Z->mapblock->data. Also, the 192x192x100 example you gave earlier has 14,400 mapblocks, with at least 2 vectors, a 512 alloc, 2=some 1024 allocs to go with each plus god knows what else that we haven't figured out and all of that is on the heap which probably puts around 100,000 items in the bucket allocator. Part of the main loop is that each of those 14,400 mapblocks has to be checked EVERY FRAME to see if the dirty bit is set. If the 16x16 mapblock is simply a #define statement and not based on actual code, changing them to 64x64 would make a bigger difference on performance than any pathfinding code change and only require changing 2 or 4 characters in the source. In many ways a 4x4 embark would become as fast as a 1x1 embark is now.. (not completely obviously)
###+####+#######
###+####+#######
###+####+#######
++++####+#######
########+#######
########+###++++
########+###+###
########+###+###
########+###+###
########+###+###
########+###+###
########+###+###
########+###+###
########+###+###
########+###+###
########+###+###The more you get into this, you will see why I hate people that are like, "derp, use this pathfinding function instead derp!" but you are clearly not one of those people now since you're analyzing the dataset so I like you now. <3
You know, starting from the viewpoint that you hate everyone until they prove themselves to you is problematic in what is fundamentally a board for persuasive argument (and this is endemic to almost all of your arguments).
Anyway, while building from the bottom up, as opposed to starting from the top down is all well and good, you have to keep in mind that these things still need to actually work.
You cannot simply cut the map into a series of 16x16x1 grids completely without regard for what is actually contained within those grids
Lets make something very clear.. pathfinding doesn't know or care about what it is looking at it. It could be looking at a massive grid, waypoint nodes, vector meshes, or even the BGP table. All it sees are paths it needs to travel to get where it wants to go. The reason I suggested changing the mapblock from 16x16 to 64x64 has nothing to do with pathfinding, since the pathfinding function itself doesn't even know the size of a mapblock. The 64x64 thing is just an example of memory optimization that would beat the snot out of anything pathfinding related while potentially only requiring the changing of 4 characters in the source. At the end of the day, pathfinding would have to process the same amount of data regardless of how the map was broken up if broken up at all.
I had to read that like 5 times to get what you guys were saying..
Are you saying that the mapblock itself is a node? If you are I can totally understand what you are saying. If you are not, disregard the rest of this post hehe :P
Designations are a separate 16x16 array per mapblock from the pathfinding data, they are for... designations like digging or channeling and such :) If it was up to me, that data would be replaced with a designation list but whatever hehe.
Right here I mean, it looks like traffic is stored as part of the designation data: https://github.com/peterix/dfhack/blob/master/library/include/dfhack/modules/Maps.h#L300
Or maybe I'm misreading.
No, you're not misreading *facepalm*. If that is true, then it means DF might be accessing more data than it needs to lol. The designation data for a mapblock is stored in a different memory allocation than the pathfinding data...
I had assumed it was packing all the data it needed for pathfinding into the pathfinding data :/ That still might be the case though, the traffic designations might be stored in both which wouldn't be a problem since its just 2 bits.
Alright, sorry, I was thinking you were talking about merging mapblock data and pathfinding into the same set of data.
If you were just talking about storing mapblock data, however, 64x64x1 z-level mapblocks can run into problems... what if you have a 2x2 embark? That's 96x96xz tiles, which means that you have to use 4 sets of 64x64, with 7168 tiles of "overlap" that contain no data per z-level.
Anyway, right now, the one true failure of the current A* system (which is to say, disregarding lag, and only focusing on the functions it seriously cannot perform) is that it doesn't actually support multitile creatures at all, and that it doesn't support swimming or flying creatures very well.
The problem with how much lag the HFS produces is that fliers seem to actually use BFS over the entire map every time they try to pathfind, even if all access into the fortress is blocked. That means flood-filling the HFS (at least) every frame for every creature.
Once an HFS finds a target, I don't believe they continue the BFS every frame, but I do believe they will seek a target until they find one-- and I don't necessarily see anything wrong with that.
Once an HFS finds a target, I don't believe they continue the BFS every frame, but I do believe they will seek a target until they find one-- and I don't necessarily see anything wrong with that. It could be and should be improved with a proper set of connectivity maps that take fliers into account, of course, but the aggressiveness isn't the problem.
HFS can be walled off once breached, which causes severe slowdowns. Furthermore, there are MASSIVE numbers of HFS, and they respawn (albeit slowly). This causes a LOT of said BFS.
Regardless though, the key here is to make a pathfinding system that is efficient for ANY movement type-- walking, flying, swimming, magma... heck, add in digging, climbing, maybe even jumping... and while we're at it, might as well add in multitile movement as well. It must be robust to handle these kinds of things.That stuff is trivial I can easily do it with my room system (have to turn simulator to 3d add obsticles of diffrent types). All I'll do is add in all the collisions of interest to the list and go through them to calsify movement type on an edge.
The whole point of threads and "slicing" is to transfer processor power onto another task while waiting for a memory fetch. This is something that has existed for decades. Thing is, DF is not multi-threaded, so all this means is that your processor will spend its time working on all the other programs running on your computer during this time.That's the point of multi-threading in a single processor environment, but that environment exists in very few places anymore. Not to derail, just to be pedantic.
That's the point of multi-threading in a single processor environment, but that environment exists in very few places anymore. Not to derail, just to be pedantic.
The whole point of threads and "slicing" is to transfer processor power onto another task while waiting for a memory fetch. This is something that has existed for decades. Thing is, DF is not multi-threaded, so all this means is that your processor will spend its time working on all the other programs running on your computer during this time.That's the point of multi-threading in a single processor environment, but that environment exists in very few places anymore. Not to derail, just to be pedantic.