OK...I am understanding you better now - sorry for being so stubborn. I think that you are totally correct and I should test out playing with a Flow Field (the next step generated from a Distance map (or my perhaps not so precise term 'heatmap') - I was assuming that since the Flowfield was generated from the same data then using it would result in the same issues and have the same benefits pretty much - but this assumption is probably very wrong.paul doe wrote: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.leopardpm wrote: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....
My use of the term 'heatmap' mostly comes from how the map is used - when I was young I remembered a game called hot/cold where one child might hide something and the other would try to find it. The child who hid it would say "Your getting hotter, hotter, oops now colder, colder" as the other child moved about looking for the hidden item - the same way these map work for pathfinding - the smaller the distances values means the 'hotter' or 'closer' to the Goal is.... it just makes sense to me, but if you think it causes confusion in talking to others then I will try to curb my usage. Though I think it is pretty silly to call a basic data structure, which is created in the same way, different things based on how it is used - I can use the same map to find a shortest path, or, to influence pathfinding in an attractive sense or a repulsive sense (stay away from danger, as you suggested earlier), or, if processed once more, to figure out the direction of movement along the path to a goal... but, if calling them different things is less confusing to others, then so be it.
BUT, just to make sure I am FULLY understanding what you mean by a Flow Map, does this program show a Flow Map?
Code: Select all
const TILEW = 40
const TILEH = 40
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
const mapsizeX = 20
const mapsizeY = 10
dim shared as integer map(mapsizeX,mapsizeY,5)
''''''' Map variable explanation
' 0 = object at location (9 = Blocker)
' 5 = Direction Vector (FLOW Value)
'
' 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) 'way over estimating
' 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 * (mapsizeX-8) + 4 : y = rnd * (mapsizeY-8) + 4
while map(x,y,0) > 0
x = rnd * (mapsizeX-8) + 4 : y = rnd * (mapsizeY-8) + 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 * (mapsizeX-2) + 1 : y = rnd * (mapsizeY-2) + 1
while map(x,y,0) > 0
x = rnd * (mapsizeX-2) + 1 : y = rnd * (mapsizeY-2) + 1
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 < (mapsizeX+1))) and ((j > 0) and (j < (mapsizeY+1))) 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
map(i,j,5) = (direct+4) mod 8 ' save flow field info
'plot it
x1 = i*TILEW
y1 = j*TILEH
c1 = rgb(200,200,200) ' degfault grey background
clrNew = 255 - (costNew/.3)
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 mapsizeX
x1 = i*TILEW
for j as integer = 1 to mapsizeY
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 mapsizeX
for j as integer = 0 to mapsizeY
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
map(i,j,5) = 0 'flow field value
next j
next i
' Put in some blocking tiles
'PutBlocker(100) ' Blocker Tiles
PutMapPF(1,5) ' Trees
MakeHeatMap(1)
locate 3,40 : Print "Distance Map for all 5 Trees"
locate 5,40 : 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
cls
for i as integer = 1 to mapsizeX
x1 = i*TILEW
for j as integer = 1 to mapsizeY
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
if map(i,j,0) = 0 then
circle(x1+(TILEW/2),y1+(TILEH/2)), 4, rgb(255,255,255)
line(x1+(TILEW/2),y1+(TILEH/2)) - step (DirInfo(map(i,j,5),0)*10,DirInfo(map(i,j,5),1)*10),rgb(255,255,255)
end if
next j
next i
locate 3,40 : Print "Flow Field for all 5 Trees"
locate 5,40 : Print "Hit <anykey> to continue"
sleep
Please also note that I do not have any 'local optima' issues simply because of the way my breadth-first flood fill tests neighbors. But, no matter how a particular routine deals with local optima, its always making a choice between two equal paths/directions/distances - there is no one 'perfect' answer, just an acceptable solution - this choice could be made randomly and still be 'correct' as far as dealing with local optima and not getting hung up during pathfinding or useage... am I correct in stating this?
------------------------------------------------------
OK, maybe we can now move on to bigger and better things....
We were talking about A* earlier and the advantages and differences between that and flowfields:
When I said 'map size does not matter', I am not saying there are not cases where an A* path could be more costly than regenerating an entire flow field map - imagine a room in a house and pathing from that room to the outside of the house.... A* will take the EXACT same time to find the path if the map size is just the same as the house and the neighborhood, OR if the map size includes every house and building in the city. The Flow Field generation will be directly slowed down in proportion to the map size. NOTE: I am NOT saying that this slowdown will make using a Flow Field too costly, just that it is something to consider when choosing the appropriate pathing routine/method.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.
THIS is helpful... and now that I think for a second, its obvious...very helpful indeed - I was thinking that I needed a priority queue (probably because Amit Patel(Red Blob Games) uses them), but since the routine will replace a value in a node with a smaller value, then the order of dealing with the nodes doesn't matter..... interesting, if I am understanding correctly...Thanks! Worth checking out anyways.BTW, you don't even need to sort the nodes by using flow fields.
My question to you is: Doesn't the memory requirement for Flow Fields become overwhelming thereby limiting their use? I envision using a Flow Field to path to a few common objects scattered across the world (Trees, resources, etc) - but wouldn't using a flowfield to path to another agent (or other object that could be 'moving' and dynamic) means that it would have to be regenerated with each change AND such a flowfield would have to be created for every possible thing to path to? Again, I could be confused somewhere - so let me see if I can speak clearly: a different flowfield is needed for every 'type' of object and since the memory requirement to hold a flowfield increases directly with the size of the map - the larger the map, then the less # of them can be used - am I correct?
Also, I wanted to mention - one reason why I don't use 'only' Flow Fields is because it is vital to the speed of my Action Planning routine to be able to retrieve the exact and perfect distance to a particular goal without spending anytime pathfinding (even trivial time like following vectors and adding up the movement costs)...and by keeping the distance map allows for that.
NOTE: Throughout this discussion I have kinda seemed to be on the side 'against' using flow fields - this is definitely NOT the case! I have always appreciated their simplicity, and especially the enormous speed gains by using them and making pathfinding virtually trivial. BUT, my understanding is that they do have certain constraints so they cannot be used effectively in all cases and sometimes other pathing routines are needed, perhaps in addition to flow fields.... do you agree?