Making heatMaps more Dynamic

[leopardpm]

What are the variable that defines the explored pixels, does it consist on the whole array defined first containing the obstacles? Or is it defined in the function you name Heatmap? As far as I can judge for now, it's all defined at start when you provide the array?

OK, first off the Map and all associated HeatMaps are in the array map(100,100,5)

Code: Select all

dim shared as integer map(100,100,5)
''''''' Map variable explanation
' 0 = object at location (9 = Blocker)
' 5 = quantity of object
'
'  the following are for cheap, fast pathfinding routine - heat/influence/flow map
'
' 1 = distance to nearest tree object (#1)
' 2 = distance to nearest iron ore object (#2)
' 3 = distance to nearest Berry Bush Object (#3)
' 4 = distance to nearest Mushroom Object (#4)

with each HeatMap associated with a specific object type (Trees, etc) with its own 'layer'.
Map(x,y,0) = tells what type of object is there (0=nothing, 1=Tree,2=Iron,etc)
Map(x,y,1) = is the Heatmap for Trees - this has the distance to the nearest Tree in it... it is initialized with '999' so that the HeatMap routine can make one test to determine if the new heatmap value is lower than this nodes current value and then replace it. SO, in answer to your question: The variable that tells if that cell has been 'explored' is the HeatMap itself... 999 = unexplored, any value = been explored BUT might not have the lowest distance, 0 = has an actual object (tree?) in cell

[leopardpm]

I don't know if you have ever visited Amit's pages before, but that is where I learned all about this stuff and A* pathfinding - his examples are pretty clear and straightforward and he does a much better job of explaining than I do about the fundamentals...

https://www.redblobgames.com/pathfinding/a-star/introduction.html
Scroll down to "Breadth First Search" because that is actually how I am generating the heatmap (I will alter it to include movement costs when necessary, and that is the difference between Breadth First Search and Dijkstra’s Algorithm)

[leopardpm]

Just tell me where are defined the boundaries of the exploration of the MakeHeatmap function, I'm not sure I can find it by myself easily enough ! ;)

these boundaries are in the array Frontier(), they are not in any order or 'region' they are in order of distance, basically - and the distance is to ANY Tree, not any certain tree (or object)

[Tourist Trap]

Just tell me where are defined the boundaries of the exploration of the MakeHeatmap function, I'm not sure I can find it by myself easily enough ! ;)

these boundaries are in the array Frontier(), they are not in any order or 'region' they are in order of distance, basically - and the distance is to ANY Tree, not any certain tree (or object)

Oh, I was about to ask you what this frontier array was about.
I see that you set 9000 as value there. the number of squares of the grid is 100x100 = 10000...
Whatever, I'll try right now to modify this frontier array and see what it does :) Thanks!

[leopardpm]

OK, you forced me to do it....

Here is the code that includes re-generating the topleft portion 20x20 of heatmap for Trees....

(note: it was much easier than I thought it would be...sorry)

Code: Select all

const TILEW = 5
const TILEH = 5

const SCRW = 1280 '100 * TILEW
const SCRH = 600 '100 * TILEH

const Red as ulong = rgb(255,0,0)
const Green as ulong = rgb(0,255,0)
const Blue as ulong = rgb(0,0,255)
const Yellow as ulong = rgb(255,255,0)
const Black as ulong = rgb(0,0,0)
const White as ulong = rgb(255,255,255)
const Gray as ulong = rgb(200,200,200)

const Trees as integer = 1
const IronOre as integer = 2
const BerryBushes as integer = 3
const Mushrooms as integer = 4

dim shared as integer map(100,100,5)
''''''' Map variable explanation
' 0 = object at location (9 = Blocker)
' 5 = quantity of object
'
'  the following are for cheap, fast pathfinding routine - heat/influence/flow map
'
' 1 = distance to nearest tree object (#1)
' 2 = distance to nearest iron ore object (#2)
' 3 = distance to nearest Berry Bush Object (#3)
' 4 = distance to nearest Mushroom Object (#4)


dim shared as integer DirInfo(7,2) ' for movement & pathfinding
' directions 0-7
' 7 0 1
' 6 x 2
' 5 4 3
'
' info 0-2: 0 = xAdj, 1 = yAdj, 2 = movecost
data 0,-1,10
data 1,-1,14
data 1,0,10
data 1,1,14
data 0,1,10
data -1,1,14
data -1,0,10
data -1,-1,14

for i as integer = 0 to 7
    for j as integer = 0 to 2
        read DirInfo(i,j)
    next j
next i

dim shared as integer frontier(9000,2)
' frontier for pathfinding (#, cost=0 x=1 y=2 )????????
dim shared as integer frontpointer

' some subroutines....
declare function FrontierAdd(ByVal frontX as integer, ByVal frontY as integer, ByVal frontCost as integer, byval ot as integer) as integer

function FrontierAdd(ByVal frontX as integer, ByVal frontY as integer, ByVal frontCost as integer, byval ot as integer) as integer
    ' this function uses and alters the shared variables: frontier(9000,2) & frontpointer

    '  ... add it to the end then bubble sort it down...
    dim as integer bub, frontHere
    frontpointer = frontpointer + 1
    frontHere = frontpointer
    frontier(frontpointer,0) = frontCost
    frontier(frontpointer,1) = frontX
    frontier(frontpointer,2) = frontY
    if frontpointer > 1 then
        bub = frontpointer
        do
            if frontier(bub,0) > frontier(bub-1,0) then
                swap frontier(bub,0) , frontier(bub-1,0)
                swap frontier(bub,1) , frontier(bub-1,1)
                swap frontier(bub,2) , frontier(bub-1,2)
                frontHere = bub - 1
            else
                bub = 2 ' early exit
            end if
            bub = bub - 1
        loop until bub < 2
    end if
    return frontHere
end function

declare function FrontierDel(ByVal thisOne as integer) as integer

function FrontierDel(ByVal thisOne as integer) as integer
    select case thisOne
        case is < frontpointer
            for i as integer = thisOne to (frontpointer-1)
                frontier(i,0) = frontier(i+1,0)
                frontier(i,1) = frontier(i+1,1)
                frontier(i,2) = frontier(i+1,2)
            next i
            frontpointer = frontpointer - 1
        case is = frontpointer
            frontpointer = frontpointer - 1
    end select
    return thisOne
end function


declare sub PutBlocker(ByVal cnt as integer)

sub PutBlocker(ByVal cnt as integer)
    dim as integer x, y
    for i as integer = 1 to cnt
        x = rnd * 92 + 4 : y = rnd * 92 + 4
        while map(x,y,0) > 0
            x = rnd * 92 + 4 : y = rnd * 92 + 4
        wend
        map(x,y,5) = 1 : map(x,y,0) = 9 ' put 1 blocker there

        ' plot it on map - not needed....
        line(x*TILEW,y*TILEH)- step(TILEW-2,TILEH-2),rgb(0,0,0),BF
    next i
    ' force an actual walls around middle...
    for x = 40 to 60
        map(x,40,5) = 1 : map(x,40,0) = 9 ' put 1 blocker there
        map(x,60,5) = 1 : map(x,60,0) = 9 ' put 1 blocker there
        line(x*TILEW,40*TILEH)- step(TILEW-2,TILEH-2),rgb(0,0,0),BF
        line(x*TILEW,60*TILEH)- step(TILEW-2,TILEH-2),rgb(0,0,0),BF
    next x
end sub

declare sub PutMapPF(ByVal ot as integer, ByVal cnt as integer)

sub PutMapPF(ByVal ot as integer, ByVal cnt as integer)
    dim as integer x, y
    for i as integer = 1 to cnt
        x = rnd * 92 + 4 : y = rnd * 92 + 4
        while map(x,y,0) > 0
            x = rnd * 92 + 4 : y = rnd * 92 + 4
        wend
        map(x,y,5) = 1 : map(x,y,0) = ot ' put 1 object(ot) there
        map(X,Y,ot) = 0 ' zero out the distance for that object
'        'add it to the 'frontier' for pathfinding
        FrontierAdd(x,y,0, ot)
        ' plot it on map
        line(x*TILEW,y*TILEH)- step(TILEW-2,TILEH-2),rgb(255,255,255),BF
    next i
end sub


declare sub MakeHeatMap(ByVal ot as integer)

sub MakeHeatMap(ByVal ot as integer)
    ' a basic Djistra's Floodfill routine, not optimized at all...
    dim as integer x,y,i,j,cost,costDir,costNew, oldPoint
    dim as integer x1, y1, c1, clrADJ, clrNew
    do
        oldPoint = frontpointer
        x = frontier(frontpointer,1)
        y = frontier(frontpointer,2)
        cost = frontier(frontpointer,0)
        ' remove point from frontier
        FrontierDel(oldPoint) 'remove current point from frontier
        ' error check
 '       if cost <> map(x,y,ot) then 'ERROR
'            beep
'            sleep
'            end
'        end if
        ' check all 8 directions, if cost to move there is less then their current cost then
        ' change their cost and add to frontier
        for direct as integer = 0 to 7
            i = x+DirInfo(direct,0) 'x Adj
            j = y+DirInfo(direct,1) 'y Adj
            if ((i > 0) and (i < 101)) and ((j > 0) and (j < 101)) then
                if (map(i,j,0)<>9) then
                    costDir = DirInfo(direct,2) ' movecost
                    costNew = cost + costDir
                    if map(i,j,ot) > costNew then
                        if map(i,j,ot)= 999 then
                            FrontierAdd(i,j,costNew,ot)
                        end if
                        map(i,j,ot) = costNew
                        'plot it
                        x1 = i*TILEW
                        y1 = j*TILEH
                        c1 = rgb(200,200,200) ' degfault grey background
                        clrNew = 255 - (costNew/1)
                        if clrNew < 0 then clrNew = 0
                        select case ot
                            case 1 ' 1 = distance to nearest tree object (#1)
                                c1 = rgb(0,clrNew,0)
                            case 2 ' 2 = distance to nearest iron ore object (#2)
                                c1 = rgb(clrNew,0,0)
                            case 3 ' 3 = distance to nearest Berry Bush Object (#3)
                                c1 = rgb(0,0,clrNew)
                            case 4 ' 4 = distance to nearest Mushroom Object (#4)
                                c1 = rgb(clrNew,clrNew,0)
                        end select
                        line(x1,y1)- step(TILEW-2,TILEH-2),c1,BF
                    end if
                end if
            end if
        next direct
    loop until frontpointer = 0
end sub


' MAIN

screenres SCRW,SCRH,32
   
    cls
    dim as integer x1, y1, c1
   
    ' draw grid
    for i as integer = 1 to 100
        x1 = i*TILEW
        for j as integer = 1 to 100
            y1 = j*TILEH
            c1 = rgb(200,200,200)
            select case map(i,j,0)
                case 1
                    c1 = rgb(0,255,0)
                case 2
                    c1 = rgb(255,0,0)
                case 3
                    c1 = rgb(0,0,255)
                case 4
                    c1 = rgb(255,255,0)
            end select
            line(x1,y1)- step(TILEW-2,TILEH-2),c1,BF
        next j
    next i
   
    randomize
    ' fill map with random objects, and init pathfinding heatmaps for each object
   
    ' initialize map distances for pathfinding....
    for i as integer = 0 to 100
        for j as integer = 0 to 100
            map(i,j,0) = 0
            map(i,j,1) = 999
            map(i,j,2) = 999
            map(i,j,3) = 999
            map(i,j,4) = 999
        next j
    next i
   
    ' Put in some blocking tiles
    PutBlocker(100) ' Blocker Tiles
       
    PutMapPF(1,40) ' Trees
    MakeHeatMap(1)
    locate 3,70 : Print "Heatmap for all 40 Trees"
    locate 5,70 : Print "Hit <anykey> to continue"
    sleep

' for Tourist Trap
'
' Clear out the topleft region 20x20 except put all those trees into the frontier
for x as integer = 1 to 20
    for y as integer = 1 to 20
        ' clear Tree heatmap
        map(x,y,1) = 999
        if map(x,y,0) = 1 then 'OOPS! Tree there!
            map(x,y,1) = 0
            FrontierAdd(x,y,0,1)
        end if
    next y
next x
makeHeatMap(1)
    locate 3,70 : Print "Remade HeatMap for top left 20x20 region"
    locate 5,70 : Print "Hit <anykey> to continue"
    sleep



           
    PutMapPF(2,5) ' Iron Ore
    MakeHeatMap(2)
    locate 3,70 : Print "Heatmap for all 5 Iron Ores"
    locate 5,70 : Print "Hit <anykey> to continue"
    sleep
   
    PutMapPF(3,10) ' Berry Bushes
    MakeHeatMap(3)
    locate 3,70 : Print "Heatmap for all 10 Berry Bushes"
    locate 5,70 : Print "Hit <anykey> to continue"
    sleep
   
    PutMapPF(4,5) ' Mushrooms
    MakeHeatMap(4)
    locate 3,70 : Print "Heatmap for all 5 Mushrooms"
    locate 5,70 : Print "Hit <anykey> to continue"
    sleep

    'draw map
    for i as integer = 1 to 100
        x1 = i*TILEW
        for j as integer = 1 to 100
            y1 = j*TILEH
            c1 = rgb(50,50,50)
            select case map(i,j,0)
                case 1
                    c1 = rgb(0,255,0)
                case 2
                    c1 = rgb(255,0,0)
                case 3
                    c1 = rgb(0,0,255)
                case 4
                    c1 = rgb(255,255,0)
                case 9
                    c1 = rgb(0,0,0)
            end select
            line(x1,y1)- step(TILEW-2,TILEH-2),c1,BF
        next j
    next i
    sleep


[paul doe]

...
BTW: I use the terms Heat map, Influence Map, Potential Field Maps, etc as interchangeable because they seem to be all generated by the same method - if I am misunderstanding these terms, please let me know!...

Very well then. They aren't the same, you see, much in the same way as a Sorted List isn't quite the same as a Priority Queue.
Let's get some facts straight first:

The core mechanics of Influence Mapping: an article explaining what an 'Influence Map' is, and what it's used for.
Clearance-based pathfinding: explains the basic algorithm to implement pathing for agents of different sizes and traversal capabilities using a variant of the Brushfire Algorithm.

Here is an example using Goal-Based Vector Field Pathfinding, which is basically the same thing as I am talking about... BUT, notice that the Potential Field is being ENTIRELY regenerated in real-time.. very slow. Also, the example has only ONE goal, not multiple.

https://gamedevelopment.tutsplus.com/tutorials/understanding-goal-based-vector-field-pathfinding--gamedev-9007

Yes, it's entirely regenerated, but it isn't neither slow nor needed. You can pretty much update it in the same way you construct it: by starting at a goal node and 'flood-filling' the nodes that need updating, and stopping the update when the nodes don't need to change. About the 'slowness': an A* query for each individual agent is far more costly. Remember, these algorithms were invented precisely to have massive amounts of units all doing pathing at the same time (the first implementation of this algo was in the game Supreme Commander).

The problem I see is that your 'heat map' generation is wrong. This is how a vector field should look (image from my implementation):

The black nodes are impassable, the red ones are unreachable, the green and orange nodes represent traversable but costly terrain (think swamp and lava, respectively). And the gray nodes represent terrain that adds a bonus to the overall cost of the path (think a road). The white nodes are normal terrain, and the green circles represent goal nodes.
Now, if you look at the map, each agent starting at any given point on the map will try to reach the closest goal node by using the most cost-efficient path available to them from that location. Hence, they'll tend to avoid costly and potentially dangerous terrain (the orange nodes), and will try to follow 'easygoing' nodes (like roads). All they have to do is follow the blue arrows that indicate the path they should take.
Although is not shown here, you can smooth paths simply by a weighted average of the surrounding nodes to get continuous instead of discrete movement.

[Tourist Trap]

OK, you forced me to do it....

Here is the code that includes re-generating the topleft portion 20x20 of heatmap for Trees....

Ahah! Thanks a lot. See now, for 20x20 it a kind of uggly a the top left pixel. But for 30x30 it's not that bad!
My best guess now is that with some overlap to be ignored, this may work. I started to study your code now in depth. But from what you just allowed, it seems really not that bad at the center of the redrawn zone, if you exclude a thick perimeter which is much darker or lighter that it should be. We are on the right path I think, or on some alternative at least.

[paul doe]

And this is the connectivity graph for the above map (yes, it's created explicitly):

Now, using an explicit connectivity graph, along with the vector field, it's a trivial matter to update it whenever something changes. Just start to flood-fill the update from the node that changed and update directions and distances accordingly.

Creating the connectivity graph explicitly also has several other advantages: you can specify portals (teleporters, anyone?), 'special' nodes that your agents can use (like elevators, switches and so on), and any other cool applications you can think of, and your agents will be able to use all this intelligently without you having to do anything special (remember, the agent is just following the arrows). Not to mention the speed gain. You see, simply iterating through the map cells and checking each neighbor for things like costs, traversability, etc. equates to calculating the connectivity graph every single time a query is made. Think about it for a second and you'll understand the impact this can have on the speed of the algo.

[leopardpm]

Paul! Glad you chimed in!

Before I reply, I want to say that I know you are a MUCH better programmer than I and probably have alot more experience than I. So, if I question or disagree in any way, don't take it personally - it is probably due to a misunderstanding on my part, BUT it could also be due to a misunderstanding on your part of what I am trying to say. Basically, I am THRILLED to have your input in this or any discussion and I really appreciate how well you comment your code...in short: Respect!

I really do understand the differences between Heat Map, influence maps, potential fields, etc, but the basic mechanics of how they are generated is pretty much the same: with Dijkstra's algorithm. Am I right? With a heatmap or Influence map, the distance values are saved in the map, whereas with potential fields, it goes one step further and saves the vectors as well. Am I right?

according to this guy:
he says:

Vector field pathfinding is composed of three steps.
(1) First, a heatmap is generated that determines the path-distance between the goal and every tile/node on the map.
(2) Second, a vector field that designates the direction to go in to reach the goal is generated.

and then:

This vector field is generated one tile at a time by looking at the heatmap. The x and y components of the vector are calculated separately, as shown in the pseudocode below:

1 - Vector.x = left_tile.distance - right_tile.distance
2 - Vector.y = up_tile.distance - down_tile.distance

with that said, I don't think my 'heatmap' generation routine is 'wrong', it does not go on and then generate the vectors for a Flow Field, but I don't see how that helps much.

I also am aware of how to incorporate terrain costs... in my example, I am just using a Breadth-First search/fill - it will take very little to change it to Dijkstra's algorithm and incorporate Terrain Costs as you did in your nice example.

Now, as far as 'slow' or 'fast'...
One agent using A* to path to a location will be faster than generating an entire Heatmap (or Vector Field), correct?
Having 1000 agents using A* to path to different locations will be much slower than generating an entire Heatmap/Vector Field.
It ALSO depends on how large the map is because the size of the overall map does not matter to A*, whereas a Heatmap takes longer in porportion to the overall size of the map.
I would like a VERY large map.....
This slowdown of generating a Heatmap (forgive me for continually using this term, I am just so used to using it loosely) can be mitigated by figuring out a routine that only regenerates the portion that has changed...as I stated in the first post.

So, the question comes down to: How many Agents will pathfind with the same HeatMap BEFORE something alters that Heatmap?

For Trees, probably alot which is why I choose to use a Heatmap for Tree Objects.
But not for agent to agent pathfinding (agent A paths to agent X, agent B paths to agent Y, agent C paths to agent M, or, agent D paths to Object A, agent E paths to Object B,etc) , where each agent is probably moving in some fashion so that MULTIPLE heatmaps would have to be re-generated each game loop (almost), then A* is probably the best way.

Although is not shown here, you can smooth paths simply by a weighted average of the surrounding nodes to get continuous instead of discrete movement.

really? That is a nice way to do it! can't wait to test that! - I was thinking of using a version of "string pulling" to smooth, with possibly some adjust near blocking tiles/objects so that agents don't hug the walls and such....

Hold on, you just posted your 'connectivity map/graph' thing and it IS very interesting... questions coming....

[leopardpm]

And this is the connectivity graph for the above map (yes, it's created explicitly):

hmmm.... so this graph shows how every node is connected with its neighbors (or any other nodes: teleporting, as you suggest)... but it needs regenerated with any change in the 'blockers', same as the HeatMap/Flow field, right?

Now, using an explicit connectivity graph, along with the vector field, it's a trivial matter to update it whenever something changes. Just start to flood-fill the update from the node that changed and update directions and distances accordingly.

um... I am not seeing the update as being so trivial.... it is trival to ADD to the map, NOT so trivial to delete an object. To delete it, one must first find the intersection of the heatmap which is directly related to the object in question AND any other heatmaps, THEN flood-fill backwards that entire area....

Unless, I am misunderstanding something... please enlighten me....

[paul doe]

Paul! Glad you chimed in!

Before I reply, I want to say that I know you are a MUCH better programmer than I and probably have alot more experience than I. So, if I question or disagree in any way, don't take it personally - it is probably due to a misunderstanding on my part, BUT it could also be due to a misunderstanding on your part of what I am trying to say. Basically, I am THRILLED to have your input in this or any discussion and I really appreciate how well you comment your code...in short: Respect!

Oh, don't worry about that. I don't need any ego-boost, just sharing what I know =D

I really do understand the differences between Heat Map, influence maps, potential fields, etc, but the basic mechanics of how they are generated is pretty much the same: with Dijkstra's algorithm. Am I right? With a heatmap or Influence map, the distance values are saved in the map, whereas with potential fields, it goes one step further and saves the vectors as well. Am I right?

Yes and no. You see, what you (and the article author, BTW) call a 'heat map' is normally called the Influence Map. This isn't really useful for pathing, but it alters the weightings of the paths so the agents avoid, say, heavily defended positions. Since you stated that you've played Warcraft 2, then a simple example will allow you to understand what I mean.

Do you remember what happened in that game when the computer consumed all the gold mines it had? The computer-controlled peons/peasants will reach for the closest mine available, and if you controlled it, all you had to do to stop it was putting a few combat units in the path of the peasants, and they'd all get killed and the AI stalled. A heat map could avoid this, simply by assigning a 'heavier' weight to that area. So, instead of choosing the closest mine, it would go for the less risky one. See? There's a difference between the flow field and the 'heat maps'. The heat maps influence the interpretation of the flow fields for the agents.

...with that said, I don't think my 'heatmap' generation routine is 'wrong', it does not go on and then generate the vectors for a Flow Field, but I don't see how that helps much.

Then you're simply not using a flow field. The flow field is what actually tells the agents the direction they need to take to reach the goal node(s), displayed as the blue arrows in the picture I showed you before. If you only use the distance to determine the path, you risk what's called a local minima (search for it) that'll get your agents stuck.

...Now, as far as 'slow' or 'fast'...
One agent using A* to path to a location will be faster than generating an entire Heatmap (or Vector Field), correct?
Having 1000 agents using A* to path to different locations will be much slower than generating an entire Heatmap/Vector Field.
It ALSO depends on how large the map is because the size of the overall map does not matter to A*, whereas a Heatmap takes longer in porportion to the overall size of the map.
I would like a VERY large map.....
This slowdown of generating a Heatmap (forgive me for continually using this term, I am just so used to using it loosely) can be mitigated by figuring out a routine that only regenerates the portion that has changed...as I stated in the first post...

How does the size of the map doesn't matter to A*? In the best cases perhaps not, but in the worst cases (a very convoluted path) you might end up scanning the entire map and, if you over-estimate the heuristic, you end up doing a very costly Dijkstra's. Flow fields allow you to do this in linear time.
You don't need to 'figure out' a routine to do it, you simply update it much in the same way you construct it, only the requirements for adding a node to the stack of considered nodes is different. BTW, you don't even need to sort the nodes by using flow fields.

So, the question comes down to: How many Agents will pathfind with the same HeatMap BEFORE something alters that Heatmap?

For Trees, probably alot which is why I choose to use a Heatmap for Tree Objects.
But not for agent to agent pathfinding (agent A paths to agent X, agent B paths to agent Y, agent C paths to agent M, or, agent D paths to Object A, agent E paths to Object B,etc) , where each agent is probably moving in some fashion so that MULTIPLE heatmaps would have to be re-generated each game loop (almost), then A* is probably the best way.

Again, it isn't as costly as you might think. Of course, you can use A* for it if you prefer (especially the annotated variant, which I published a link before). You don't need to regenerate it each loop, you can distribute the pathing over multiple game ticks.

Although is not shown here, you can smooth paths simply by a weighted average of the surrounding nodes to get continuous instead of discrete movement.

really? That is a nice way to do it! can't wait to test that! - I was thinking of using a version of "string pulling" to smooth, with possibly some adjust near blocking tiles/objects so that agents don't hug the walls and such...

If you want to avoid 'wall hugging', then you can use Influence around each wall, to repel agents coming close while pathing. Did you read the link I posted before? It contains some ideas on this.

[paul doe]

And this is the connectivity graph for the above map (yes, it's created explicitly):

hmmm.... so this graph shows how every node is connected with its neighbors (or any other nodes: teleporting, as you suggest)... but it needs regenerated with any change in the 'blockers', same as the HeatMap/Flow field, right?

Again: a heat map and a flow field are NOT the same concept. You only need to regenerate the links to that node, not the entire connectivity graph. And the flow field is updated starting at the node that changed.

um... I am not seeing the update as being so trivial.... it is trival to ADD to the map, NOT so trivial to delete an object. To delete it, one must first find the intersection of the heatmap which is directly related to the object in question AND any other heatmaps, THEN flood-fill backwards that entire area....

Unless, I am misunderstanding something... please enlighten me....

I don't think I follow your terminology, at all. What do you mean with 'intersection of the heat map'? And with 'flood-fill backwards'?
Both adding and deleting objects is about the same. Why should it be otherwise? Agents and/or other dynamic objects aren't part of the flow field nor the connectivity graph!.

[leopardpm]

having issues posting images... trying to use the same service that Paul Doe is (imgbox), and tried both the 'link' code and the 'url' code but neither are showing up in the forum.... argh!

[leopardpm]

hmmm... lots of questions, one at a time... sorry for the crazy sized pictures... I haven't uploaded pictures in some time and am having issues...

first off, I understand local minima - basically when there are 2 or more equal choices.... usually there is some hack or adjustment to correct for it.

You say that Flow Fields are not affected by local minima... can you show me the flow fields for this map, starting from either the Triangle or Circle and going to the other? In particular I am interested in the cells with the little x in them...ACTUALLY, I drew the map wrong - the cells I am interested in most are the ones directly above and below the vetical line of black blocked cells....sorry. My Heatmap generator (the Breadth-First flood fill), there should not be any local minima due to the method of testing adjacent cells...
I am understanding that since Flow Fields are made from the underlying Heatmap, they are just as affected by local minima unless some sort of adjustment is added during the Flow Field creation process....


you said:

what you (and the article author, BTW) call a 'heat map' is normally called the Influence Map. This isn't really useful for pathing, but it alters the weightings of the paths so the agents avoid, say, heavily defended positions.

I disagree - with the heatmaps I generated with the posted program, I can trace out the exact same path as would a Flow Field would, if going cell by cell - the flow field allows 'any angle' pathing, which I am not implementing, but if I were, that would be one reason to go ahead and generate the flow field from my heatmap. A heatmap is only different from an influence map in how they are used, NOT in how they are created so much.

Maybe I misunderstand something... could you show me how you create your flow fields? I am assuming you do a Dijkstra floodfill for distance values then create the Vectors based on that.... Because from the example on this thread:
I don't see any difference between that and what I would create from my heatmap(which is distance values)...

again, there seems to be a fundamental misunderstanding, either on my part (thinking that a flow field is created from a heatmap (which is a distance map created with Breadth-First floodfill (for uniform movement cost grids) or Dijkstra floodfill (for variable movement costs for terrain, etc)) or on your part in my using terms incorrectly....

and this is possibly going to highlight where the issue is:

Again: a heat map and a flow field are NOT the same thing. You only need to regenerate the links to that node, not the entire connectivity graph. And the flow field is updated starting at the node that changed.

OK, I can see where in the connectivity graph, only the links to that node need to be regenerated. BUT, the Flow Field not only needs the starting node, but also needs to figure out where to stop - the points of where it stops is what I was referring to as the 'intersection of the heatmap of other objects'

To graphically explain:

here is a basic heatmap, except that it counts diagonal movement the same as orthagonal (I really should have written a program but somehow I thought using a paint program would be 'easier'...ug...). All the numbers are the distances to the 'closest' tree. To pathfind from any point, find the lowest value of all the adjacent cells to that point and move there, then do it for that cell and so on until hit the Tree. To generate a flowfield map from this heatmap, for every cell, put a vector in it pointing to the adjacent cell which is lowest cost.... in the case of two or more adjacent cells, then pick one as they are all 'correct'. NOW, lets say we are going to delete the Tree in the Green Shaded area. That tree's individual 'heatmap' is the entire green shaded area and ALL those cells need to be regenerated... this is true for a heatmap, OR, for the consequently created Flow Field map. to regenerate this area, my thought is to start from the tree and clear out each neighboring cell UNTIL you hit the point where the values are decreasing instead of increasing - this means that you are now in another Tree's heatmap area (the blue or red shaded area).... put all the locations of this delineation between heatmaps into the Frontier and now use Dijkstra back towards the cell where the tree was (this is what I meant when I said a 'reverse Dijkstra' which was a confusing and not correct term).

Please tell me where I am off track in my thinking compared to yours because I think we are basically saying the same thing but are confused in either the terms or how we explain it to each other....

[paul doe]

...
first off, I understand local minima - basically when there are 2 or more equal choices.... usually there is some hack or adjustment to correct for it....

Sorry, my bad. The term is local optima, not minima. And no, it's not that. Read the link you posted before to understand what it is. It is what you call the 'heat map' what causes these, not the flowfield. How you resolve this issue is up to you (the link proposes one solution). And no, you don't need to resort to hacks to make it work correctly on a cell-by-cell basis.

...You say that Flow Fields are not affected by local minima... can you show me the flow fields for this map, starting from either the Triangle or Circle and going to the other?

No, they shouldn't, if you construct them right (the article author just uses a 'naîve' approach):

I left the distances in the picture for you to be able to figure out what the problem with just using the distances is.

...
you said:

what you (and the article author, BTW) call a 'heat map' is normally called the Influence Map. This isn't really useful for pathing, but it alters the weightings of the paths so the agents avoid, say, heavily defended positions.

I disagree - with the heatmaps I generated with the posted program, I can trace out the exact same path as would a Flow Field would, if going cell by cell - the flow field allows 'any angle' pathing, which I am not implementing, but if I were, that would be one reason to go ahead and generate the flow field from my heatmap. A heatmap is only different from an influence map in how they are used, NOT in how they are created so much.

Have it your way then. Of course they are created the same way, that's why I told you they were different concepts: they apply to different things. Call it however you wish, but be aware that you might confuse someone that actually knows what you're talking about.

...
Maybe I misunderstand something... could you show me how you create your flow fields? I am assuming you do a Dijkstra floodfill for distance values then create the Vectors based on that.... Because from the example on this thread...:
...I don't see any difference between that and what I would create from my heatmap(which is distance values)...

Then just go ahead with that. My implementation is way over your head ATM (if the Metaballs demo, which is straightforward, blew your mind...). Use the image above and compare your 'heat map' with the distance field generated for such a case. If they're similar, then you don't have to worry about local optima.

...
and this is possibly going to highlight where the issue is:

Again: a heat map and a flow field are NOT the same thing. You only need to regenerate the links to that node, not the entire connectivity graph. And the flow field is updated starting at the node that changed.

OK, I can see where in the connectivity graph, only the links to that node need to be regenerated. BUT, the Flow Field not only needs the starting node, but also needs to figure out where to stop - the points of where it stops is what I was referring to as the 'intersection of the heatmap of other objects'

Thus, to update it, you only need the starting node. Start at that, and stop when the direction of the flow field doesn't need to change. This is NOT the same as saying 'the distance doesn't need to change' because the direction could, in fact, need to be adjusted to account for the change. You really need to implement a flow field to understand how the distance field differs from the vector field.

...
To graphically explain:
...
<snip>
...
Please tell me where I am off track in my thinking compared to yours because I think we are basically saying the same thing but are confused in either the terms or how we explain it to each other....

Nah, you're hell-bent in thinking that a distance field (what you call a 'heat map') and a flow field are the same thing. They're not. Calculating the distance field is the first step in implementing a flow field. Just try to implement actual movement of agents using just the distance field and you'll be able to understand how they differ, and the caveats involved.