Print

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

[Niseg]

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

I spiced up your map for you  by adding some "trees "(link )

Code: [Select]

_0123456789abcdef
0##################
1#+#+++#++#+#+++#+#
2#+++#+#++++#+#+++#
3#+#+++###+##+++#+#
4#++++++#+++++#+++#
5#######++++#######
6#+#++##++#+#+++++#
7#++#++#++++#+++++#
8#+#+++++++#++++++#
9#######+#++#######
a#+++++#++#+#+#+++#
b#++#++#++++#+++#+#
c#++++#+++++++#+++#
d##################

You might find it  a tad harder to slice it up but it should result in the same tree.  I did notice that BFS is usually give Red corners (childless ) and when entering a room you get greens/yellows which means lots of connections.  I can probably scan for reds and backtrack to greens or follow reds to find corners .

My current BFS is not optimal . I'm planning a full code rewrite adding custom classes  which would allow more features and adding   multiple searches algorithm support .  I did a damage calculator for a game in JS it's not the best but it's fairly functional ( it parses the game files directly so updating it is really easy) . 

[Mohican]

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

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.

Code: [Select]

##################   ##################   ##################
#+++++#++++#+++++#   #+++++#++++#+++++#   #+++++#++++#+++++#
#+++++#++++#+++++#   #+++++#++++#+++++#   #+++++#++++#+++++#
#+++++###+##+++++#   #+++++###+##+++++#   #+++++###+##+++++# 
#++++++++++++++++#   #++++++++++++++++#   #++++++++++++++++#
#######++++#######   #######++++#######   #######++++#######
#+++++#++++#+X+++#   #+++++#++++#AAAAA#   #+++++#++++#     # we choose randomly a X , there is only one.
#+++++#++++#+++++#   #+++++#++++#AAAAA#   #+++++#++++#     #
#++++++++++++++++#   #+++++++++++AAAAA#   #+++++++++++X    #
#######++++#######   #######++++#######   #######++++#######
#+++++#++++#+++++#   #+++++#++++#+++++#   #+++++#++++#+++++#
#+++++#++++#+++++#   #+++++#++++#+++++#   #+++++#++++#+++++#
#++++++++++++++++#   #++++++++++++++++#   #++++++++++++++++#
##################   ##################   ##################


Code: [Select]


##################   ##################   ##################
#+++++#++++#+++++#   #+++++#++++#+++++#   #+++++#++++#+++++#
#+++++#++++#+++++#   #+++++#++++#+++++#   #+++++#++++#+++++#
#+++++###+##+++++#   #+++++###+##+++++#   #+++++###+##+++++#
#++++++++++++++++#   #++++++++++++++++#   #++++++++++++++++#
#######++++#######   #######++++#######   #######++++####### we choose randomly a X , and call it Y
#+++++#++++#     #   #+++++#++++#     #   #+++++#++++#+++++#
#+++++#++++#     #   #+++++#++++#     #   #+++++#++++#+++++#
#BBBBBBBBBBBBBBBB#   #XXXXX XXXX      #   #XXXXX XXYX      #
#######++++#######   #######++++#######   #######++++#######
#+++++#++++#+++++#   #+++++#++++#+++++#   #+++++#++++#+++++#   
#+++++#++++#+++++#   #+++++#++++#+++++#   #+++++#++++#+++++#   
#++++++++++++++++#   #++++++++++++++++#   #++++++++++++++++#   
##################   ##################   ################## 
 

Code: [Select]


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



Code: [Select]


##################   ##################
#+++++#++++#+++++#   #+++++#++++#+++++#
#+++++#++++#+++++#   #+++++#++++#+++++#
#+++++###+##+++++#   #+++++###+##+++++#
#++++++X XX++++++#   #++++++X YX++++++#
#######    #######   #######    #######
#+++++#    #     #   #+++++#    #     #
#+++++#    #     #   #+++++#    #     #
#XXXXX           #   #XXXXX           #
#######    #######   #######    ####### 
#+++++#    #+++++#   #+++++#    #+++++#   
#+++++#    #+++++#   #+++++#    #+++++#   
#DDDDDDDDDDDDDDDD#   #XXXXX      XXXXX#   
##################   ################## 



Code: [Select]


##################   ##################
#+++++#++E+#+++++#   #+++++#++X+#+++++#
#+++++#++E+#+++++#   #+++++#++X+#+++++#
#+++++###E##+++++#   #+++++### ##+++++#
#++++++X EX++++++#   #++++++X  X++++++#
#######  E #######   #######    #######
#+++++#  E #     #   #+++++#    #     #
#+++++#  E #     #   #+++++#    #     #
#XXXXX   E       #   #XYXXX           #
#######  E #######   #######    ####### 
#+++++#  E #+++++#   #+++++#    #+++++#   
#+++++#  E #+++++#   #+++++#    #+++++#   
#XXXXX   E  XXXXX#   #XXXXX      XXXXX#   
##################   ################## 



Code: [Select]


##################   ##################
#+++++#++X+#+++++#   #+++++#++X+#+++++#
#+++++#++X+#+++++#   #+++++#++X+#+++++#
#+++++### ##+++++#   #+++++### ##+++++#
#++++++X  X++++++#   #++++++Y  X++++++#
#######    #######   #######    #######
#FFFFF#    #     #   #     #    #     #
#FFFFF#    #     #   #     #    #     #
#FFFFF           #   #                #
#######    #######   #######    ####### 
#+++++#    #+++++#   #+++++#    #+++++#   
#+++++#    #+++++#   #+++++#    #+++++#   
#XXXXX      XXXXX#   #XXXXX      XXXXX#   
##################   ##################



Code: [Select]


##################   ##################
#+++++#++X+#+++++#   #+++++#++X+#+++++#
#+++++#++X+#+++++#   #+++++#++Y+#+++++#
#+++++### ##+++++#   #+++++### ##+++++#
#GGGGGGGGGGGGGGGG#   #XXXXX      XXXXX#
#######    #######   #######    #######
#     #    #     #   #     #    #     #
#     #    #     #   #     #    #     #
#                #   #                #
#######    #######   #######    ####### 
#+++++#    #+++++#   #+++++#    #+++++#   
#+++++#    #+++++#   #+++++#    #+++++#   
#XXXXX      XXXXX#   #XXXXX      XXXXX#   
##################   ##################



Code: [Select]


##################   ##################
#+++++#HHHH#+++++#   #+++++#    #+++++#
#+++++#HHHH#+++++#   #+++++#    #+++++#
#+++++### ##+++++#   #+++++### ##+++++#
#XXXXX      XXXXX#   #XXXXX      XYXXX#
#######    #######   #######    #######
#     #    #     #   #     #    #     #
#     #    #     #   #     #    #     #
#                #   #                #
#######    #######   #######    ####### 
#+++++#    #+++++#   #+++++#    #+++++#   
#+++++#    #+++++#   #+++++#    #+++++#   
#XXXXX      XXXXX#   #XXXXX      XXXXX#   
##################   ##################



Code: [Select]


##################   ##################
#+++++#    #IIIII#   #+++++#    #     #
#+++++#    #IIIII#   #+++++#    #     #
#+++++### ##IIIII#   #+++++### ##     #
#XXXXX      IIIII#   #XXXXX           #
#######    #######   #######    #######
#     #    #     #   #     #    #     #   the last steps are trivial
#     #    #     #   #     #    #     #
#                #   #                #
#######    #######   #######    ####### 
#+++++#    #+++++#   #+++++#    #+++++#   
#+++++#    #+++++#   #+++++#    #+++++#   
#XXXXX      XXXXX#   #XXXXX      XXXXX#   
##################   ##################


[Draco18s]

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?

[NW_Kohaku]

Well, at a certain point, we are optimizing for several different priorities at once - we need to optimize the amount of time it takes to build the graph, optimize the time it takes to use the graph, optimize the memory usage of the graph, and optimize the functionality of the graph.

At some point, we can generally just say "screw it", and go with a sub-optimal graph that takes more time to path through than a purely optimal graph, just because we wanted to make the graph itself faster, and just took a reasonable guess.

I also think that having some sort of end-of-the-season stop-and-sweep-up-any-mess-in-the-graph phase to make sure that we can try to put together some optimal paths might be a nice way of getting some balance in the performance, so that long-unchanged paths can be assured of optimization would be a decent way to make sure some heavily used paths are optimized without having to jump through a more complex optimization process very frequently.


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]

##################
Ω.Ω.Ω.<<Ω.<<Ω.Ω.Ω#
<<<<<<Ω.<<Ω.<<<<<+
Ω...Ω...Ω...Ω...Ω#
>>>>>.Ω>>.Ω>>>>>>+
Ω.Ω.Ω>>.Ω>>.Ω.Ω.Ω#
##################


[Mohican]

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?

I've edited my previous post with showing what X I choose each step (I call it Y).
I use these rectangles to be sure to not have a "bad" graph like:

Code: [Select]

AAB
DCB
DEE
It is a possible repesentation of a rectangle that could be trivially represented as one node.
The "depth" of the graph using maximal rectangle is minimal (but there are more connections between nodes), so it's a sure way (the representation is unique) to have a quite optimised representation..

[Niseg]

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:

Code: [Select]

##################
#s+++++++#d++++++#
#+##############+#
#++++++++#+#+#+#+#
#+########+#+#+#+#
#++++++++#+#+#+#+#
#+########+#+#+#+#
#++++++++#+#+#+#+#
#+########+#+#+#+#
#++++++++#+#+#+#+#
#+########+#+#+#+#
#++++++++++++++++#
#++++++++++++++++#
##################

as the A * trys to take the shortest path it would check endless dead-ends.
dividing it up into rooms :

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

  G H I
         \|/
S-A-B-C-E-F-J-D

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

[Mohican]

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:

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

Do you have a method to be sure your map will be sliced like this and not like that:

Code: [Select]

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

[Draco18s]

Mohican:
While sub-optimal, it's still fewer nodes (in the end that are saved) than the original A* path.

[Mohican]

Mohican:
While sub-optimal, it's still fewer nodes (in the end that are saved) than the original A* path.

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.

[NW_Kohaku]

Um, guys?... Any response on this?

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]

##################
Ω.Ω.Ω.<<Ω.<<Ω.Ω.Ω#
<<<<<<Ω.<<Ω.<<<<<+
Ω...Ω...Ω...Ω...Ω#
>>>>>.Ω>>.Ω>>>>>>+
Ω.Ω.Ω>>.Ω>>.Ω.Ω.Ω#
##################


[kaenneth]

Um, guys?... Any response on this?

Spoiler (click to show/hide)

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]

##################
Ω.Ω.Ω.<<Ω.<<Ω.Ω.Ω#
<<<<<<Ω.<<Ω.<<<<<+
Ω...Ω...Ω...Ω...Ω#
>>>>>.Ω>>.Ω>>>>>>+
Ω.Ω.Ω>>.Ω>>.Ω.Ω.Ω#
##################


retangular section could also have a 'density' attribute, for example, if the number of path blocking objects is less than the square root of the area/shortest edge

valid:

Code: [Select]

..........
.......Ω..
....Ω.Ω...
.....Ω....
..Ω..Ω....
..........
....Ω.....
..........
...Ω..Ω...
..........

invalid:

Code: [Select]

..Ω.......
..Ω.......
..Ω.......
..Ω.......
..Ω.......
..Ω.......
..Ω.......
..Ω.......
..Ω.......
..Ω.......

One idea that's been stirring in my mind is to use fixed size range 'blob' fills (I just made that up, if it has some other specific meaning, or if there is already a name for this, I dunno) to define areas, that is, you pick a point, and flow out from it by picking the nearest open unclaimed open space until you've filled up to your target blob size; then spawn new blobs from the edges. If a blob falls under half the target size, it merges with it's smallest neighbor blob, if it goes over double the target size, it splits by cutting out a new blob being formed from the edge furthest from the center of mass. And blobs would not be restricted to one z-level.

So, starting with this map...

Code: [Select]


############
#..#.#.#.#.#
#..........#
#.##########
#..........#
##########.#
#..........#
##########.#
#..........#
##########.#
#..........#
############

a blob size of 8 leads to:

Code: [Select]

############
#aa#a#b#b#d#
#aaaabbbbbb#
#a##########
#ccccccccee#
##########e#
#fffffffeee#
##########e#
#igggggggge#
##########h#
#jjjhhhhhhh#
############

merging the undersized blobs (d, i, j) to their larger neighbors:

Code: [Select]

############
#aa#a#b#b#b#
#aaaabbbbbb#
#a##########
#ccccccccee#
##########e#
#fffffffeee#
##########e#
#ggggggggge#
##########h#
#hhhhhhhhhh#
############

So the connections are a-b, a-c, c-e, e-f, e-g, e-h;

I think this method would make it very easy to not only fit to irregular areas, but also adapt to local changes; a newly dug square would just get appended to the smallest neighboring blob without cascading to resectioning the entire map.

I'm going to code a version of this in a DF-like model world to validate it can always reach a stable state quickly; and that effects can't cascade more than a couple blobs. it's possible a split could orphan multiple sections section that get re-merged, triggering a re-split... it might do to just place a limit on the depth of recursion allowed in rebalancing, if a blob is a couple tiles over the alleged 'limit', it's not a big problem.

Variable blob sizes might be an interesting DF specific optimization as well; say make an tile with a built object count double for the size; and doors quardruple, so that a row of furnished bedrooms would create clusters of small blobs, while outdoor areas and empty halls would allow larger ones.

I also need to think about how to store these blobs in memory efficently... that'll probably be the problem with this approach.

[Artanis00]

Um, guys?... Any response on this?

Spoiler (click to show/hide)

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]

##################
Ω.Ω.Ω.<<Ω.<<Ω.Ω.Ω#
<<<<<<Ω.<<Ω.<<<<<+
Ω...Ω...Ω...Ω...Ω#
>>>>>.Ω>>.Ω>>>>>>+
Ω.Ω.Ω>>.Ω>>.Ω.Ω.Ω#
##################


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?

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]

##################
#.#.#.#.#.#.#.#.##
##.#.#.#.#.#.#.#.#
#.#.#.#.#.#.#.#.##
##.#.#.#.#.#.#.#.#
#.#.#.#.#.#.#.#.##
##.#.#.#.#.#.#.#.#
#.#.#.#.#.#.#.#.##
##.#.#.#.#.#.#.#.#
#.#.#.#.#.#.#.#.##
##.#.#.#.#.#.#.#.#
#.#.#.#.#.#.#.#.##
##.#.#.#.#.#.#.#.#
#.#.#.#.#.#.#.#.##
##.#.#.#.#.#.#.#.#
#.#.#.#.#.#.#.#.##
##.#.#.#.#.#.#.#.#
##################

For comparison, worst-case for unaided A* is a wide, contiguous up/down stair column, so YMMV.

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.

[Draco18s]

If we're doing convex polygons, then your diagonal hallway there IS a convex polygon, therefore can be one node.

[Starver]

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.

Of course, convex polygons give a more possible optimisations.  Although this is also their problem, as you have to consider the issue with the modified Manhattan approach to distance[1] that means that these optimisations are more complicated to find, and at the same time harder to dispel in favour of a more optimal optimisations...  Which is where my own vain pursuit of algorithmic perfection is probably holding me back.  (If I dare kid myself that I have a hope in hell of attaining such an ideal!)

And the code for "Are we inside this polygon" is less simple, you have to check dot product calculations between the line defined by each adjacent pair of corner-nodes (in a consistent direction around that polygon) and the point being tested, to find that this point is on the "inside" of every single one of these.  Unless there's something more efficient that I'm not aware of.  (The main alternative is sub-dividing the convex area into a set of rectangles and triangles, and do the standard in-a-rectangle test on all orthogonal boundaries, and a vastly simplied "above/below, and left/right" test on the diagonals if it lies within an angled corner.)

You also have to ensure that your 'straight line' algorithm between two node points (for one polygon, heading in one direction, for an adjacent-fitting polygon, heading the other direction) does not either mutually bypass a tile, or mutually claim one.  Unless you're using a system in which your polygons are meant to share border tiles (for path calculation purposes, along all routeing border areas) in which case both must agree on which those bi-zone (multi-zone, at a polygon corner intersection) border tiles are.

Complexities that might make for a ☼Masterwork☼ end result, but possibly at the expense of the xTatteredx nerves of a programmer, if not setting his eyeballs !!Aflame!! during the debugging and testing process.



[1]

Code: [Select]

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

[Draco18s]

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.