Print

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

[Draco18s]

Although personally I wouldn't use a tiered hierarchy for the nodes.  I'd use a mesh.

Under the assumption that every group of tiles has the same "edge" weight (as far as A* is concerned) it would actually return the red path:

S, door, hall (orange), hall, (pale orange), hall (yellow), door, F
As it would be shorter than:
S, door, hall (orange), "central tower", hall (orange), hall (pale orange), door, F

Depending on how the tiles are grouped.

Obviously you'd want some weighting for each grouping, but you'd have to balance between using an abnormally high value for a long skinny hallway that the dwarf only needs to walk 3 tiles to cross, or an abnormally short distance for a long skinny hallway that the dwarf needs to walk the 37 tiles down.

Although it may be possible to determine these values when the mesh is built, giving each edge a weight based on the distance, or at least one that is "close enough" that it works.

For instance, on square nodes the weight would be the side length (the only path that is longer are the diagonals, but not by much).  For rectangles (especially ones that exceed a 1:2 length to width ratio) the weight would be the distance across the rectangle perpendicular to the connecting face.  So a node connection on the long face has a weight of the length of the short face; connections would be direction independent (the node you're entering).

This would mean that the length would be artificially low if the dwarf has to cross and travel down a long hallway, but is an acceptable failure to find the "shortest" path, as all we need is a sufficiently efficient path using the fewest processing cycles as possible.

So our red path above is an approximated length 26, the blue 45 (using the node boundaries as drawn).  In reverse the distances are 23 (red) and 51 (blue).  Actual distances are 27 (red) and 34 (blue).

[Niseg]

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.

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]

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)

Code: [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 .

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.

Finding a hash for the room is a trivial problem it got to do with deciding on data structures and data organization. It's not such a big issue because as you said the X,Y,Z coordinates  of points inside the room are unique.

[NW_Kohaku]

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]

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)

Code: [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?

Also, this whole plan seems to have nothing for vertical pathfinding - how will fliers and swimmers be able to pathfind using this?

[Niseg]

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?

The bit vector will tell which nodes within the rectangle are members of  the room .
example:

Code: [Select]

_01234567
0#######
1#+#+++#
2#+###+#
3#+++#+#
4#+###+#
5#+#+++#
6#+###+#
7#+++++#
8#######

room A is 1,1 to 3,7
room B is 3,1 to 5,7
those rooms overlap but they have a disjoint node set
binary mask for room A

Code: [Select]

100
100
111
100
100
100
111

binary mask for room B

Code: [Select]

111
001
001
001
111
001
001
011

This way two squares may overlap but not include the same nodes.

Also, this whole plan seems to have nothing for vertical pathfinding - how will fliers and swimmers be able to pathfind using this?

I don't think I accounted for that - when the dwarf/mob reach a blocked  "room"  it can try to find an alternate path when it finds out the original one is blocked - then the room can be updated to show that the connection with another node has been severed .

It's also true that a dwarf/mob would wants to go  through 100 z levels you'll have to go through 100 "rooms"  but it's not as bad because you'll have a simple traversal on each step of the way. 

[Draco18s]

You did it wrong again.

The question was for a layout like this:

_01234567
0#######
1#+#+++#
2#+###+#
3#+++#+#
4#+###+#
5#+#+++#
6#+###+#
7#+++#+#
8#######

[Niseg]

You did it wrong again.

The question was for a layout like this:

_01234567
0#######
1#+#+++#
2#+###+#
3#+++#+#
4#+###+#
5#+#+++#
6#+###+#
7#+++#+#
8#######

It doesn't really matter where the walls are when we are talking which open spaces are included in each node. There is also nothing that stops us from adding walls to a room. you just change the last lines of the masks of room A and room B to  111 and 001 respectively and you get a disjoint set of nodes.

[NW_Kohaku]

What I'm asking relates to how you are talking about 16x16 blocks to make a node, and then talking about them as though multiple nodes are stored in the same block of data or the like...

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.

[Niseg]

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.

You can keep drawing maps it doesn't really matter if each node has a rectangle + a bit map where a 1 says "this node is in the room " and 0 say "this zone is not in this room"
so now all you got is 1,1 to 3,8 and 3,0 to 5,7

 A    B
100 | 100
100 | 111
111 | 001
100 | 001
100 | 001
111 | 111
001 | 001




 It doesn't really matter what shape room you have you can describe it with a bit vector. The 16X16 was generally an example of how to store it. with a bitmap you can actually need only 1 point and you can store winding corridors if you want to .
something like this with 3 rooms all overlapping each other in some way :

Code: [Select]

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


[Draco18s]

The point was, what determines connectivity from one room to another?  All you're doing is storing the same data in a new way.

[Niseg]

The bit vector only solves the shape problem. The edges of the nodes would require more data types that store edges.

Code: [Select]

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;

after determining the rooms you need to do a connection graph using edges data type.
after that's done.

There is another option . You can store the nodes in  a 2 dimensional array and then use something like an 8 bit mask for open directions

example:

Code: [Select]

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

Managing this data type would be complicated. but node traversal would be faster .Using nodes with edge list within them is trivial but it might cost in some cache performance and more memory. .The edge list can store a complex type with a clear destination point/points  but this is not that important. I think we are talking about 2MB on 4X4 embarks and with a node data type with 6 edges (with destination points) it's about 100 bytes per node that's about 47MB if each room is on average size 16  or 4X4  (this number should be maximized). To reach that maximum you'll practically have to dig out every level into a maze  and have 200 levels of stone/soil

This takes care of irregular shaped rooms and their connection. Dividing the map into room and their dynamic update(merge,grow,delete etc...) is another issue. I did cover some of it in my general post about the "rules".

[NW_Kohaku]

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.

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

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

While the psuedo-search tree/massively hierarchical method I was speculating on may be somewhat wonky, it does at least return a path with minimal searching of unnecessary nodes.  (I'm still thinking of ways to try to make the system work better... If I make it a floating independent data structure with freak loads of pointers, it stays light, and it is possible, if potentially very confusing, to have children of unrelated higher-tier nodes as your own node's branches.  I'm just not sure how to make that work in a cost-effective manner, yet.) 

Without such a method, the heuristic gets a little odd, although I think you were talking about using a heuristic based upon just making a node address out of hashing the xyz coordinates before, so I guess that's what you're thinking. 

[Niseg]

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 .

If you only store the open spaces the node graph shouldn't take much room .

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

I hope you'll find my partial response satisfactory I gotta drive home .

Anyways with all the parameters defined it's just a matter of implementing a demo - everyone is welcome to it .

[Zanielyene]

Does toady even read this thread?

I always thought caching commonly used paths would be helpful. ie: caching the path between workshops and stockpiles.

I imagine with only a few megabytes of cache, quite a few paths could be cached, reducing the load on the cpu.

[Draco18s]

The problem there is determining a commonly used path.  You'd have to save every path request and check for frequency before you could even start saving those common paths.  And requests that are 1 tile off from a "known" request is unique, as far as the computer is concerned.

[Niseg]

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 imagine with only a few megabytes of cache, quite a few paths could be cached, reducing the load on the cpu.

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.
 
It all comes down to creating a map to  prevent the cpu of using tunnel vision. It's stuck in the maze and it won't move until it finds a path out. With a map It would be easier for it to tell the way and avoid looking through known dead ends.