Print

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

[NW_Kohaku]

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.

[Niseg]

So you are suggesting a new node weighing scheme .   Claiming that a path exists to any destination using a "beaten path ". This way major nodes would be most visited node. If you the number of nodes to N you can cache (N-1)^2 paths from popular nodes.

Then pathing algorithm would be like this :
1. find minimal heuristic score of all popular nodes from the destination and source
2. find a path from the closest popular node closest to the destination
3. if such a path exist find a path to the popular node closest to you.
4. use a predefined path to the node closest to destination.
5. use pre-calculated path to destination.

This can work well for path caching. you can also give the user the option to pin their popular nodes rather than the OS to do it. This can allow pathing to run faster  with a relatively minor cost and low complexity to implement. It does have a pitfall.
side view

Code: [Select]

S_A_B
##X#X
##X#X
##X#X
##X#X
##X#X
##C#D
#####


C is closer to D but the path from C to D is much longer than the path from B to D. As we all know heuristic can lie. we can try to limit it and make it look for a better candidate It might be less expensive than doing the long path.

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 . You can also add run length encoding for repeated steps. Using this figure you can (without run length ) fit 5242 paths per 1MB which can store the connections between 102~ major nodes.  for 200 nodes you'll need about 4MB and for 1000 you'll need 100MB.

I guess this is a good alternative to a complex room scheme.

[NW_Kohaku]

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.

[Niseg]

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.

My comment was related to path caching /highway generation and which has a much different scheme than my original suggestion of problem reduction.

My original  suggestion  was to build a map of smaller areas from the original map and navigate it changing
 the complexity from O(f(W*x)) to O(x*f(W)+f(M)).

here is a small example to clarify

Code: [Select]

##################
#+++++#++++#+++++#
#++A++#++B+#++C++#
#+++++###+##+++++#
#++D+++++E++++F++#
#######++++#######
#+++++#++++#+++++#
#++G++#++H+#++I++#
#++++++++++++++++#
#######++++#######
#+++++#++++#+++++#
#++K++#+J++#+++L+#
#++++++++++++++++#
##################
room division

Code: [Select]

  B   C
  |   |
A-D-E-F-C
    |
  G-H-I
    |
  K-J-L

path caching ,highway N=A+L+B where L>> A (much greater ) and L>>B. M is number of nodes that make the highway gives a O( f(A)+f(B) +2*M ) the search of M can be reduced to log M by ordering the nodes. Node placement either using a statistic scheme or manual placement.

Code: [Select]

A-B 2SE,3E,1NE,N,stop
A-C 2SE,7E,2NE,E,stop
A-D 2S,stop
.
.

There are now two different  solutions well defined solution  (I hope ) which reduce the complexity of Pathing. There is  generally more advantage to creating a map over path caching but mapping is tougher to implement.  Path caching is fairly simple to implement once you decide on a node placement scheme but the paths you'll get as results won't be ideal and may require some "smoothing".

[Draco18s]

You're still not getting it.

How would it work in this situation?

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

[Niseg]

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.
 

[NW_Kohaku]

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

Keep in mind, if we allow hallway nodes to be 4x64 tiles, then we could potentially have much longer hallways with much more rooms sticking off of them, plus many different stairwells, creating potentially hundreds of connections to a single node.  But you're only talking about 10 connections to a single node.

[Draco18s]

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

Tada.  Hence why you can't say "a node can only have 8 horizontal connections (+2 for up/down)."

which method and what constraints?

Your most recent example.

[DrDada]

What about the thing this guy said?

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

I had the same idea and searched in this and other threads for it, but nobody gave feedback to it afaik.
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.

[NW_Kohaku]

What about the thing this guy said?

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

I had the same idea and searched in this and other threads for it, but nobody gave feedback to it afaik.
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.

The closest thing that you could apply would be the bias/weighting of hierarchical nodes I was talking about a little up the page:

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.

[Starver]

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.

On top of that[1], never mind that there's got to be some sort of sanity-check.  Just because dwarfs have been walking all the way around/across a mountain transferring goods from a dead-end front entrance to a dead-end rear entrance, when the player realises that this is happening and all he or she should need to do is tunnel through/unforbid the door between the sites, it's quite possible that the 'well-travelled' bias value on the mountainside route still makes it dominate the path-search over the more direct route.

Yes, hard cases make bad rules, but that's just an extreme version of something that needs to be considered before that suggestion is to be taken on-board.  Perhaps considered an acceptable side-effect, of course, and allowed to happen.


[1] Because one way of getting around that is to only 'create' reference values when walked over, and remove "flatlined' areas from the store altogether, in a dynamic and hash-like structure that doesn't attempt to store every single walkable tile, but only those having recent footsteps over them justify the slight[2] extra overhead for such a structure-lookup system and get a value, quickly getting culled.

[2] Or not.  I might let the development environment handle that sort of thing, but if we're talking about optimisation one really needs to work out how it can be done best.  Several of the ideas I have on how this might be done take up a large amount of memory (or time) in and of themselves.  If the limit on cells being stored is small enough, there could be a sorted list to binary-search containing pointers to where value is being held (if not the value itself, if that's more efficient and there aren't other bits of info being also stored there) but that would mean doing a splice-in for every single newly stepped-on tile...  Although the periodic devaluing operation could at least pull in the existing list and create a new list with reduced values in a very quick loop, discarding all the ones that hit the current 'floor' value.  Larger 'lists' would cause increasing referencing overheads, of course, on-top of their own basic footprint.

[Niseg]

which method and what constraints?

Your most recent example.

I can do both 



_012345678
0#########
1#..#.#..#
2#.......#
3#..#.#..#
4####Y####
5#..#.#..#
6#.......#
7#..#.#..#
8####.####
9#..#.#..#
A#.......#
B#..#.#..#
C####Z####
D#..#.#..#
E#.......#
F#..#.#..#
G####.####


With Path Caching I'll pick 2 or 3 way-points like Y= 4,4 and Z=4,C. This way there would be 1 path cached from Y->Z  go south 8 steps and it's reverse path .

If you want to go from 1,E to 7,1 you'll find a path from 1,E to Z, go on a path  from Z to Y  and then find a path from Y to 7,1. If you want to go to a closer node you might find that the distance to the node itself is closer than the way-point and you'll just path to it. You can also use the way-point twice  but it won't gain you much at all.  Adding 4 waypoints at the passages would make it even easier because the central hall would be the highway and your longest path would always be length 3 or less. You should also consider an O(n) path optimization/smoothing to prevent  the mob from crowding the way-points and going on unnecessary  paths.

If I was 6X6 room maximum(to complicate things ) a simple slicing algorithm would have the first room

_012345
0######
1#..#.#
2#.....
3#..#.#
4####.#
5#..#.#

after the room is generated it need to be walled off to check if it's valid

_01234567
0#######
1#######
2#..#.##
3#.....#
4#..#.##
5####.##
6#..#.##
7#######

now this room needs to be validated - every node should be reachable and it's not  so line 5 5 in the original room is either removed or has it's 5,1 and 5,2 discarded. next we can try to reshape the room to reach maximum coverage line 5 is a good candidate to be discarded because it has more nodes out of it than in it.  this way we can change from a 6X6 to a 5X7
or this

_01234567
0########
1#..#.#..
2#.......
3#..#.#..
4####Y###

do the same thing to validate and you get a good room to start with. This require all sorts of node exchange functions and validity checks. After you are done with defining rooms you can check the connections between them and define it as edges. That would give you something like this

A-B-C-D-E

this way if you want to get from 1,E to 7,1 again you'll need a path from D to A and would get  D->C->B->A-> 7,1. This gives you a couple of A* searches length 5 which in most case would be a straight line. The original problem is a 14+ step path which can reach very high complexity than the sum of it's parts.


I'm trying to sort out a JS demo for both but I need to fix up my UI. The bus ride didn't let me code much - it was a combination of baby screaming for attention and my very long arms.

[Draco18s]

Just to point out:
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?

_012345
0######
1######
2###..#
3###...
4###..#
5######/

What it the rooms were larger (rather than the quick and dirty 2x3 rooms I made)?

#######++#######
#+++++#++#+++++#
#+++++#++#+++++#
#++++++++++++++#
#+++++#++#+++++#
#+++++#++#+++++#
#######++#######
#+++++#++#+++++#
#+++++#++#+++++#
#++++++++++++++#
#+++++#++#+++++#
#+++++#++#+++++#
#######++#######
#+++++#++#+++++#
#+++++#++#+++++#
#++++++++++++++#
#+++++#++#+++++#
#+++++#++#+++++#
#######++#######

[Niseg]

For the examples here I kept room the room spiting to small sizes.In game it would be better to make them large and greedy. I'm still unsure about a reasonable slicing scheme but in generally the rooms should be reasonably large and they should also try to be as wide open as possible (vector pathing is your friend if you can do it).  A set of rules can translate into code which would translate into a map.The advantage of a room method would be that you can keep subdividing the map into a simpler  map . The room method also allows for arbitrarily large worlds without major loss of FPS due to long paths. The main disadvantage is the amount of coding and design it would take to create it.

In most of the examples here I'd group it all into 1 or 2 nodes .  The grouping system simplify long range travel. Short range traveling is generally too simple to even consider. Even with the A* worst case example you don't really need a lot of rooms - you just need to turn it from a west ->east problem to a south-> east->north problem . As I said room system is a very complicated solution but it has major advantages.

A path caching to way-points scheme is very easy to add. Toady can give the user a set of 20 waypoints  and he'll save caches of all the paths between them . This way first thing anyone pathing would do is call the heuristic about 1+2*20 times. once for source destination and then 20 src<->waypoint and 20 dst<->waypoint.  With smart placement the players can simplify very long distances into a very simple highway.  With this system you got 1 major advantage - no complicated placement scheme and very a deterministic code .  The players would plant the waypoints and they would generate a huge FPS gain .


edit : minor changes to my simple test program (too lazy to rewrite it)
- added ability to add waypoints
- added ability to set start point
- added ability to set destination point
- the bfs now search from start point if it's valid

edit2: another major update to my test program - started using some simple CSS 
- squared the maze
- added A star NAVIGATION I got from 46 dogs's blog( I got reference to it on the page)
- added path highlighting

edit3:
- Path caching done using user set waypoints (display processing time for generation)
- Find path renamed to Find Path A*
- "Find Path using  waypoints" was Added. This uses the path cache to generate path from source to destination it's about a factor of 10 faster than a* with good placement. there is no path smoothing yet. it uses the method I described above to find 2 intermediate to the cached path.
- removed the bfs maze to prevent confusion


have fun
edit4: future plans:
-expand the maze... done~

-add a better save/load function ...in progress
-add path cache size and optimized cache size(it currently saves 4byte per steps and I want to change it to 4bits per step or less)
-path smoothing to prevent zigzag into the waypoint (haven't looked into how it's done but shouldn't be tough)
-when the maze is bigger we'll talk  about optimizations , automatic placement  etc small mazes have their limitations....
- the room splitting pathing algorithm is up next ...
edit5:
- expanded the grid to 32X32  nodes (framed in 34X34 box)
- modified save/load function to support loading  old format and save/load new v01 format :v01RRCCM* R=rows C=columns M= HEX representation binary maze data.
- fixed some waypoint deleting bugs not updating cache correctly - there is still a bug when 1 waypoint is closest to both source and destination
- forum output now shows the contents of the maze which include waypoints an start/destination
-changed waypoint symbol from '$' to 'w'.
more future stuff I'll add:
-load parameter shrinking(it's huge now) - run length encoding,  LZW or switch to b64(256-> 170 byte)
-load maze from edit box (quick pasting to forum)
-maze size  scaling (or something) and maze forum output scaling
-maybe better maze visuals .
-clickable "paint tools"
 

[Reelyanoob]

Just to point out:
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)?

[...]

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.

EDIT Here's my thoughts on pathing (i might edit this with any refinements) :-

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.

Store only a list of zones which must be traversed, greatly reducing memory use. For pathing costs during the search for a good node-to-node path, use the distance from the incoming portal to the exit portal within each zone. Dwarves travelling would only need to remember the list of zones still to come, and only need to reference the current/next zones and walk straight towards the portal for the new zone.

Mark the portals(only) in the tiles they occupy, this is so that locking a door / adding a wall can trigger changes in node info on each side (the rest of the portal can be checked to see if it still allows travel).

If manually adding the zones is the chosen implementation, or if single-square nodes are used, then there may be gaps between zones. This is where storing the path on the map tiles themselves would be handy, when a door on a known path is locked or a wall built, the system would try to find a new path between the zones using normal A*, rejecting paths if they venture into other known zones (or hit a node with a better existing path to the destination), and severing the (direct) link completely if no route is found.

My last suggestion is - overlapping zones. e.g zones would include the walls surrounding them, the overlap areas would become the portals used for navigating, this would need no (or less) special markers to place on the map.