Print

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

[Artanis00]

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

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

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?

You're probably right on the rebuilding thing. I was mainly thinking that limiting the size of an individual node would also limit the volume that an A* or whatever would have to cover for internal navigation, especially since this method makes it easy to delay calculation of later parts of the path (for example, to when the creature gets to that node).

[Soralin]

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.

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

[Mohican]

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.

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

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 you are right the node building function could work with just the ability to add a node , merge 2 nodes , and split a node, and that's it. So pretty easy and not much calcultation to do.

[Artanis00]

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.

I am currently putting another dent in my wall with my forehead. So frigging obvious that I needed someone else to point it out to me...

The worst part is that while I was writing that I was thinking that flying creatures could just straight line when they're in those now-rather-pointless 16x16x16 nodes...

Just one question: 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. If you consider this system to be two levels of addressing specifically for path finding, then those objects are not addressable because they are not in nodes. But building destroyers need to get to those to destroy them, and dwarves need to get to them (as well as natural walls) to deconstruct or dig. Ideas?

[Niseg]

I played with my BFS function this weekend(in Israel Sunday is a work day) and managed to mess it up - luckly i use my website as "backup" and it's such a basic function it's not a big deal. I'll probably rewrite it especially due to its inefficiency .

My plan was to create rooms by doing an incremental BFS .  I found an easy way to do it. BFS uses a queue of nodes and pushes new nodes it visits . All i need to do to have mutiple starting points is push multiple nodes (starting points) at the beginning  and then I might be interested to mark the "starting point" when I visit node. Then I'll get a "ridge map" I'll use to slice up the map into rectangles.

I'm worried about an arbitrary slice up getting conditions where you get illogical room setups like this :

Code: [Select]

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

I might just add A*algorithm for runtime checking. I am also looking into getting this silly JS from a c structure  to a more of object oriented structure. The program I made is fairly simple and JS is really easy to learn . JS can also load website  hosted files local files is a problem..

[Starver]

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

But, that is definitely complicating things.

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



[1] Which it may not be.  If you have a troupe of invaders with digging or deconstruction ability, but only rarely would you get one, you could make a special-case pathing (if necessary, brute-force, tile-by-tile search without much reference (if any) to the established nodes.  However, you just know that if they're made a special case, someone will rue the incompatible code later on, right?

[2] Split into surface-swim-to and whole-volume-swim-to, possibly.  If not also something for creatures that water gives no impedance (or fear of drowning, at least for a while), but can't actually swim, so that their routing nodes would be on the bottom of rivers, reservoirs, etc, essentially treating wet ditches as if they were dry, etc...  And then double all of those to differentiate between water-swim and magma-swim.

[3] Another complication there.  Hostile diggers might be mapped as coming out of as yet unrevealed caverns.  And at the same time the possibility of a goblin sapper team tunnelling away a short-cut into a fortress and hitting your pre-filled "magma cavity wall" trap would be funny as well.  Really, this point is probably moot until omniscient pathfinding is no longer the norm, though.

[Draco18s]

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.

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.

[Mohican]

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.

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.

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.
Then every tiles could be represented by a graph representing walkable/non-walkable/swimable/flyable/other(all types of workshops) cuboid.

[Uristocrat]

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

[Starver]

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

[Uristocrat]

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.

Yeah, I just meant that it was only necessary (at most) to cache a few routes for them.  You shouldn't need to worry about rebuilding your overall map data to suit them.  Waste of time and memory

The best way to speed up a computer is to give it less work to do.  Eliminating stuff that creates complications is one way of doing that.

[NW_Kohaku]

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.

[Draco18s]

Obstensibly, yes.  You'll be starting with a base map that doesn't need to take into account things like workshops, but I'm saying that when a workshop is built, it should do certain things to the node map.

[Mohican]

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.

[NW_Kohaku]

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.

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.