Making heatMaps more Dynamic

Game development specific discussions.
leopardpm
Posts: 1795
Joined: Feb 28, 2009 20:58

Re: Making heatMaps more Dynamic

Post by leopardpm »

paul doe wrote:
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....
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.
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.

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
I just want to make sure that I am not missing something vital in my understanding.

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:
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.
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.
BTW, you don't even need to sort the nodes by using flow fields.
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.


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?
leopardpm
Posts: 1795
Joined: Feb 28, 2009 20:58

Re: Making heatMaps more Dynamic

Post by leopardpm »

Sorry about the multiple questions/multiple posts - I know it makes it hard to respond to each and every one.... but...

In regards to partial regeneration of the Flow Field - I am assuming that the underlying DIstance Map needs to be regenerated first, right?

We seem to be in agreement as to how that is accomplished, correct me if I am wrong, please:

(1) start with the node that has changed(deleted)

(2) iterate outwards while clearing the values of each node until reach the nodes where the Vectors have changed (or, in the case of the Distance Map, where the Distance Value starts decreasing)

(3) Add all these 'barrier nodes' to the Frontier (I am calling them 'barrier' nodes due to the fact that they reflect the point where the vectors will start pointing towards a different goal than the one we are dealing with... a 'barrier' or demarcation line)

(4) If the node has 'moved' instead of just being deleted, then also add the new location to the Frontier as well

(5) ...and then do a Floodfill (Breadth-First or Dijksta dependingon use of variable movement costs) using the Frontier

and this will allow the Flow Field to be relatively dynamic with little processing time (compared to regenerating the entire map Flow Field)... right?

or is there another way?
leopardpm
Posts: 1795
Joined: Feb 28, 2009 20:58

Re: Making heatMaps more Dynamic

Post by leopardpm »

hmmm.... my program works, but has a big flaw somewhere--- the distances are not correct, must be in my sort or floodfill.... the program is a mess at this point anyways... need to start from scratch to make it more clear and correct...

figured out the bug, fixed... but still haven't re-written the code and is very sloppy, just about to put in the Re-Generation code:

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

'==============================================
type dmapinfo
    as ushort dist
    as ubyte  pntr
    as ubyte  dirVect
end type

type mainmap
    as ubyte Obj
    as dmapinfo DMInfo(1 to 4) '1=tree, 2=iron, 3=bush, 4=mush
end type

dim shared as mainmap map2(mapsizeX, mapsizeY)

'==============================================
type dinfo
    as byte xAdj
    as byte yAdj
    as byte mCost
end type

dim shared as dinfo DirInfo(7) ' for movement & pathfinding
' directions 0-7
' 7 0 1
' 6 x 2
' 5 4 3
'
' info: xAdj, yAdj, 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
    read DirInfo(i).xAdj
    read DirInfo(i).yAdj
    read DirInfo(i).mCost
next i

'==============================================
type frontierPQ
    as ushort Cost
    as ushort x
    as ushort y
    as ushort objNum
end type

dim shared as frontierPQ frontier(2000)
dim shared as integer fPntr

'==============================================

dim shared as integer Remove(1)

type resource
    as ushort health
    as ushort x
    as ushort y
end type
dim shared as resource WorldResource(100, 1 to 4)

'==============================================

' some subroutines....
declare function FrontierAdd(ByVal frontX as integer, ByVal frontY as integer, ByVal frontCost as integer, byval ot as integer, byval treeNum as integer) as integer
function FrontierAdd(ByVal frontX as integer, ByVal frontY as integer, ByVal frontCost as integer, byval ot as integer, byval treeNum as integer) as integer
    ' this function uses and alters the shared variables: frontier(9000,2) & fPntr

    '  ... add it to the end then bubble sort it down...
    dim as integer bub, frontHere
    fPntr = fPntr + 1
    frontHere = fPntr
    frontier(fPntr).Cost = frontCost
    frontier(fPntr).x = frontX
    frontier(fPntr).y = frontY
    frontier(fPntr).objNum = treeNum
    if fPntr > 1 then
        bub = fPntr
        do
            if frontier(bub).cost > frontier(bub-1).cost then
                swap frontier(bub) , frontier(bub-1)
                frontHere = bub - 1
            else
                exit do ' 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 < fPntr
            for i as integer = thisOne to (fPntr-1)
                frontier(i) = frontier(i+1)
            next i
            fPntr = fPntr - 1
        case is = fPntr
            fPntr = fPntr - 1
    end select
    return thisOne
end function

declare sub CreateResource(ByVal ot as integer, ByVal cnt as integer) 
sub CreateResource(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 map2(x,y).obj > 0
            x = rnd * (mapsizeX-2) + 1 : y = rnd * (mapsizeY-2) + 1
        wend
        
        map2(x,y).obj = ot             ' put 1 object(ot) there
        map2(x,y).DMInfo(ot).pntr = i
        map2(x,y).DMInfo(ot).dist = 0  ' zero out the distance for that object
        
'        'add it to the 'frontier' for pathfinding
        FrontierAdd(x,y,0, ot, i) ' i is the Tree # Index

'        ' add it to WorldResource() array
        WorldResource(i,ot).x = x
        WorldResource(i,ot).y = y
        WorldResource(i,ot).health = 100
    next i
end sub

declare sub MakeDistanceMap(ByVal ot as integer)
sub MakeDistanceMap(ByVal ot as integer)
    ' a basic Djistra's Floodfill routine, not optimized at all...
    ' Assumes Frontier hold correct objects....
    '
    dim as integer x, y, i, j, cost, costNew, oldPoint, objPntr
    dim as integer x1, y1, c1, clrADJ, clrNew
    do
        oldPoint = fPntr
        cost     = frontier(fPntr).cost
        x        = frontier(fPntr).x
        y        = frontier(fPntr).y
        objPntr  = frontier(fPntr).objNum
        
        ' remove point from frontier
        FrontierDel(oldPoint) 'remove current point from frontier

        ' 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).xAdj
            j = y+DirInfo(direct).yAdj
            if ((i > 0) and (i < (mapsizeX+1))) and ((j > 0) and (j < (mapsizeY+1))) then
                if (map2(i,j).obj <> 9) then
                    costNew = cost + DirInfo(direct).mCost
                    x1 = i*TILEW
                    y1 = j*TILEH
                    if map2(i,j).DMInfo(ot).dist > costNew then
                        if map2(i,j).DMInfo(ot).dist = 999 then
                            FrontierAdd(i,j,costNew,ot, objPntr)
                        end if
                        
                        map2(i,j).DMInfo(ot).dist    = costNew
                        map2(i,j).DMInfo(ot).dirVect = (direct+4) mod 8  ' save flow field info
                        map2(i,j).DMInfo(ot).pntr    = objPntr
                        
                        'plot it
                        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
                    'erase distance value box
                    line(x1+16,y1+15)- step(16,10),rgb(200,200,200),BF
                    'put new distance value in box
                    draw string (x1+17,y1+17), str(map2(i,j).DMInfo(ot).dist), rgb(0,0,255)
                end if
            end if
        next direct
    loop until fPntr = 0
end sub

' MAIN
    dim as integer x1, y1, c1, clrNew, ot
    screenres SCRW,SCRH,32
    randomize
    
    ' initialize map distances for pathfinding....
    for i as integer = 0 to mapsizeX
        for j as integer = 0 to mapsizeY
            map2(i,j).obj = 0
            map2(i,j).DMInfo(1).dist = 999
            map2(i,j).DMInfo(2).dist = 999
            map2(i,j).DMInfo(3).dist = 999
            map2(i,j).DMInfo(4).dist = 999
        next j
    next i
        
    CreateResource(1,5) ' Trees
    MakeDistanceMap(1)
    locate 3,40 : Print "Distance Map for all 5 Trees"
    locate 4,25 : print "The values shown are the distances from the nearest Tree"
    locate 5,40 : Print "Hit <anykey> to continue"
    sleep

    cls
    ot = 1
    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)
            clrNew = 255 - (map2(i,j).DMInfo(ot).dist/.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
            if map2(i,j).obj = 0 then
                circle(x1+(TILEW/2),y1+(TILEH/2)), 8, rgb(255,255,255),,,,f
                line(x1+(TILEW/2),y1+(TILEH/2)) - step (DirInfo(map2(i,j).DMinfo(1).dirVect).xAdj*13,DirInfo(map2(i,j).DMinfo(1).dirVect).yAdj*13),rgb(255,255,255)
                line(x1+(TILEW/2),y1+(TILEH/2)) - step (DirInfo(map2(i,j).DMinfo(1).dirVect).xAdj*13,DirInfo(map2(i,j).DMinfo(1).dirVect).yAdj*13),rgb(255,255,255)
            end if
            draw string (x1+17,y1+17), str(map2(i,j).DMinfo(1).pntr), rgb(0,0,0)
        next j
    next i
    locate 3,40 : Print "Flow Field for all 5 Trees"
    locate 4,35 : print "(also showing which Tree is Nearest)"
    locate 5,40 : Print "Hit <anykey> to continue"
    sleep
EDIT: Rewrote most of code and cleaned it up a bit, used UDTs instead of my craziness.. should be much easier to follow, and the displayed output is cleaner
Tourist Trap
Posts: 2958
Joined: Jun 02, 2015 16:24

Re: Making heatMaps more Dynamic

Post by Tourist Trap »

leopardpm wrote: ........
Rewrote most of code and cleaned it up a bit, used UDTs instead of my craziness.. should be much easier to follow, and the displayed output is cleaner
Very nice!
It's a pitty that I find it so hard to go throught your style of coding. Not your fault of course (the convention of naming are too specific, I can't see what is a Fronteer function for instance, and so on). Anyway congratulation, you made clearly a step forward with this field computation.

Here, I finally managed to make some addition to the inital code we started with. I absolutly don't know what you do there in depth. But I added some interactivity. You can select a rectangle on the map, and push the button at the right and refresh the zone. You can cancel also a selection with the button2. It makes it easier to test the first idea we discussed at first.

Code: Select all

'adapted and refactored for convenience from the leopardpm's great piece of original code

#include "fbgfx.bi"

const TILEW => 18
const TILEH => 12
dim shared as integer map(any,any,any)
dim shared as integer xSize =>	40
dim shared as integer ySize =>	49
const SCRW => 1000	'100 * TILEW
const SCRH => 600	'100 * TILEH


type DBUTTON
	public:
	enum _BTNBEHAVIOUR
	  _useDelay   = -1
	  _standard   = 0
	end enum '_BTNBEHAVIOUR
    declare constructor()
    declare constructor(byval as integer, _
                   byval as integer, _
                   byval as string)
    declare constructor(byval as integer, _
                   byval as integer, _
                   byval as integer, _
                   byval as integer, _
                   byval as string, _
                   byval as _BTNBEHAVIOUR=_BTNBEHAVIOUR._useDelay, _
                   byval as double=0.5)
	declare property Behaviour() as _BTNBEHAVIOUR
	declare property Behaviour(byval as _BTNBEHAVIOUR)
    declare property ClickTimeInterval() as double   
    declare property ClickTimeInterval(byval as double)
    declare property LastClickTime() as double
    declare sub DrawButton()
		as string   _text
		as boolean  _mouseOver
		as boolean  _mouseClick
		as boolean  _mouseLegalIntervalClick
    private:
    declare sub TestButton()
		as integer			_topLeftCornerX
		as integer			_topLeftCornerY
		as integer			_bottomRightCornerX
		as integer			_bottomRightCornerY
		as _BTNBEHAVIOUR	_behaviour
		as double			_lastClickedTime
		as double			_minClickTimeInterval
end type 'DBUTTON
constructor DBUTTON()
    dim as integer scrW, scrH
    if screenPtr()=0 then
		scrW = 200
		scrH = 200
    else
		screenInfo scrW, scrH
    end if
   '
    with THIS
		._text				=> "DBUTTON"
		._topLeftCornerX		=> (scrW - 8*len(._text))\2
		._topLeftCornerY		=> (scrH - 20)\2
		._bottomRightCornerX	=> (scrW - 8*len(._text))\2 + 56
		._bottomRightCornerY	=> (scrH + 10)\2
		._mouseOver			=> FALSE
		._mouseClick			=> FALSE
		._lastClickedTime		=> 0
		._behaviour			=> DBUTTON._BTNBEHAVIOUR._standard
		._minClickTimeInterval	=> 0.5
		._mouseLegalIntervalClick	=> FALSE
    end with 'THIS
end constructor 'DBUTTON explicit default constructor
constructor DBUTTON(byval TLCX as integer, _
			           byval TLCY as integer, _
			           byval Text as string)
    with THIS
		._text					=> Text
		._topLeftCornerX		=> TLCX
		._topLeftCornerY		=> TLCY
		._bottomRightCornerX	=> ._topLeftCornerX + 8*len(._text)
		._bottomRightCornerY	=> ._topLeftCornerY + 15
		._mouseOver				=> FALSE
		._mouseClick			=> FALSE
		._lastClickedTime		=> 0
		._behaviour				=> DBUTTON._BTNBEHAVIOUR._standard
		._minClickTimeInterval		=> 0.5
		._mouseLegalIntervalClick	=> FALSE
    end with 'THIS
end constructor 'DBUTTON(valINT,valINT,valSTR)
constructor DBUTTON(byval TLCX as integer, _
					byval TLCY as integer, _
					byval BtnWidth as integer, _
					byval BtnHeight as integer, _
					byval Text as string, _,
					byval BtnBehaviour as DBUTTON._BTNBEHAVIOUR=-1, _
					byval CTI as double=0.5)
    if BtnHeight<15 then BtnHeight = 15
    with THIS
		._topLeftCornerX		=> TLCX
		._topLeftCornerY		=> TLCY
		._bottomRightCornerX	=> ._topLeftCornerX + BtnWidth
		._bottomRightCornerY	=> ._topLeftCornerY + BtnHeight
		._text				=> left(Text, BtnWidth\8)
		._mouseOver			=> FALSE
		._mouseClick		=> FALSE
		._lastClickedTime	=> 0
		._behaviour			=> DBUTTON._BTNBEHAVIOUR._standard
		._minClickTimeInterval		=> CTI
		._mouseLegalIntervalClick	=> FALSE
    end with 'THIS
end constructor 'DBUTTON(valINT,valINT,valINT,valINT,valSTR)
property DBUTTON.Behaviour() as DBUTTON._BTNBEHAVIOUR
	'---->
	return THIS._behaviour
end property 'get BUTTON_BTNBEHAVIOUR:=DBUTTON.Behaviour
property DBUTTON.Behaviour(byval SetValue as DBUTTON._BTNBEHAVIOUR)
	THIS._behaviour = SetValue
end property 'set DBUTTON.Behaviour(valBUTTON_BTNBEHAVIOUR)
property DBUTTON.ClickTimeInterval() as double 
	'---->
	return THIS._minClickTimeInterval
end property 'get DBL:=DBUTTON.ClickTimeInterval   
property DBUTTON.ClickTimeInterval(byval SetValue as double)
	THIS._minClickTimeInterval = SetValue
end property 'set DBUTTON.ClickTimeInterval(valDBL)
property DBUTTON.LastClickTime() as double
	'---->
	return THIS._lastClickedTime
end property 'get DBL:=DBUTTONLastClickTime
sub DBUTTON.TestButton()
	dim as integer gmX, gmY, gmBtn1
	getMouse gmX, gmY, , gmBtn1
	'
    with THIS
		if gmX>._topLeftCornerX				and _
				gmY>._topLeftCornerY		and _
				gmX<._bottomRightCornerX	and _
				gmY<._bottomRightCornerY	then
			if ._mouseOver=FALSE then ._mouseOver = TRUE
			if gmBtn1=+1 then
			if ._mouseClick=FALSE then ._mouseClick = TRUE
				if (TIMER - ._lastClickedTime)>._minClickTimeInterval then
					THIS._lastClickedTime = TIMER
					if ._mouseLegalIntervalClick=FALSE then _
					            ._mouseLegalIntervalClick = TRUE
					else
					if ._mouseLegalIntervalClick=TRUE then _
					    		._mouseLegalIntervalClick = FALSE
				end if
			else
				if ._mouseClick=TRUE then ._mouseClick = FALSE
				if ._mouseLegalIntervalClick=TRUE then _
				              ._mouseLegalIntervalClick = FALSE
			end if
		else
			if ._mouseOver=TRUE then ._mouseOver = FALSE
			if ._mouseClick=TRUE then ._mouseClick = FALSE
			if ._mouseLegalIntervalClick=TRUE then _
			                  ._mouseLegalIntervalClick = FALSE
		end if
    end with 'THIS
end sub 'DBUTTON.TestButton()
sub DBUTTON.DrawButton()
    dim as integer scrW, scrH, depth
    if screenPtr()=0 then
		scrW    = 200
		scrH    = 200
		depth   = 032
		screenRes scrW, scrH, depth
		windowTitle "opened by DBUTTON"
    else
		screenInfo , , depth
    end if
	'
    dim as ulong btnColor
    with THIS
		.TestButton()
		if ._mouseClick=TRUE then
		  select case depth
		     case 32
		        if ._behaviour=-1 then
		           btnColor = rgb(100,180,240)
		        else
		           btnColor = rgb(100,240,100)
		        end if
		     case else
		        if ._behaviour=-1  then
		           btnColor = 10
		        else
		           btnColor = 11
		        end if
		  end select 'depth
		elseif ._mouseOver=TRUE then
		  select case depth
		     case 32
		        if (TIMER - ._lastClickedTime)<._minClickTimeInterval and _
		                                         ._behaviour=-1 then
		           btnColor = rgb(100,180,240)
		        else
		              btnColor = rgb(200,100,200)
		        end if
		     case else
		        if (TIMER - ._lastClickedTime)<._minClickTimeInterval and _
		                                         ._behaviour=-1 then
		           btnColor = 10
		        else
		              btnColor = 13
		        end if
		  end select 'depth
		else
		  select case depth
		     case 32
		        if (TIMER - ._lastClickedTime)<._minClickTimeInterval and _
		                                         ._behaviour=-1 then
		           btnColor = rgb(100,180,240)
		        else
		              btnColor = rgb(80,100,140)
		        end if
		     case else
		        if (TIMER - ._lastClickedTime)<._minClickTimeInterval and _
		                                         ._behaviour=-1 then
		           btnColor = 10
		        else
		              btnColor = 7
		        end if
		  end select 'depth
		end if
		'   
		line (._topLeftCornerX, ._topLeftCornerY)-_
				(._bottomRightCornerX, ._bottomRightCornerY), _
				btnColor, _
				bf
		draw string (._topLeftCornerX + 1, ._topLeftCornerY - 1 + (._bottomRightCornerY - _topLeftCornerY)\2), _
				left(._text, (._bottomRightCornerX - ._topLeftCornerX)), _
				0
    end with 'THIS
end sub 'DBUTTON.DrawButton()

type RECT
	declare constructor()
	declare constructor(Tx as uinteger, Ty as uinteger, W as uinteger, H as uinteger)
	declare sub DrawRectangleOnGrid(GW as integer, GH as integer)
		as integer	_topLeftCornerX
		as integer	_topLeftCornerY
		as integer	_width
		as integer	_height
End Type
constructor RECT()
	'
End Constructor
constructor RECT(Tx as uinteger, Ty as uinteger, W as uinteger, H as uinteger)
	with THIS
		._topLeftCornerX	=> Tx
		._topLeftCornerY	=> Ty
		._width				=> W
		._height			=> H
	end with
End Constructor
sub RECT.DrawRectangleOnGrid(GW as integer, GH as integer)
	var byref tx	=>	THIS._topLeftCornerX
	var byref ty	=>	THIS._topLeftCornerY
	var byref w		=>	THIS._width
	var byref h		=>	THIS._height
	'
	line (tx -1 , ty -1 ) - step (w + 2, h + 2), rgb(200,100,100), B
	line (tx , ty ) - step (w, h), rgb(200,100,100), B
	line (tx , ty ) - step (w, h), rgba(200,0,200, 50), BF
End Sub

type RECTSELECTOR
	declare constructor()
	declare sub TestMouse()
	declare sub DrawRectangleSelector()
		as RECT		_rectSelection
		as boolean	_selectionIsRunning
		as boolean	_hasMouseFirstClicked
		as boolean	_hasMouseSecondClicked
		as boolean	_hasMouseCancelClicked
End Type
constructor RECTSELECTOR()
	with THIS
		._rectSelection							=> RECT(TILEW\2, TILEH\2, xSize*TILEW, ySize*TILEH)
		._selectionIsRunning					=> FALSE
		._hasMouseFirstClicked					=> FALSE
		._hasMouseSecondClicked					=> FALSE
		._hasMouseCancelClicked					=> FALSE
	end with
end constructor
#define	_MIN(a, b)	iif((a)<(b),(a),(b))
#define	_MAX(a, b)	iif((a)>(b),(a),(b))
sub RECTSELECTOR.TestMouse()
	dim as integer	gmX, gmY, gmWheel, gmBtn
	getMouse		gmX, gmY, gmWheel, gmBtn
	'
	if gmX>(-1 + TILEW\2) andAlso gmX<(xSize*TILEW + TILEW\2) andAlso gmY>(-1 + TILEH\2) andAlso gmY<(ySize*TILEH + TILEH\2) then
		if not THIS._selectionIsRunning then
			if gmBtn=1 then
				if not THIS._hasMouseFirstClicked then
					THIS._selectionIsRunning = TRUE
					THIS._hasMouseFirstClicked = TRUE
					with THIS._rectSelection
						._topLeftCornerX	= gmX
						._topLeftCornerY	= gmY
						._width				= 4
						._height			= 4
					end with
				end if				
			end if
		else
			if not gmBtn=0 then
				if gmBtn=1 then
					if abs(THIS._rectSelection._topLeftCornerX - gmX)<>0 andAlso _ 
									abs(THIS._rectSelection._topLeftCornerY - gmY) then
						with THIS._rectSelection
							._width				= -(._topLeftCornerX - gmX)
							._height			= -(._topLeftCornerY - gmY)
						end with
					end if
				elseIf gmBtn=2 then
					THIS._selectionIsRunning = FALSE
				end if
			else
				THIS._selectionIsRunning = TRUE
				THIS._hasMouseFirstClicked = FALSE
			end if
		end if
	end if
end sub
sub RECTSELECTOR.DrawRectangleSelector()
	THIS.TestMouse()
	'
	if THIS._selectionIsRunning then
		THIS._rectSelection.DrawRectangleOnGrid(TILEW, TILEH)
	end if
end sub



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 tSize =>	5
redim shared as integer map(xSize,ySize,tSize)

' directions 0-7
' 7 0 1
' 6 x 2
' 5 4 3
dim shared as integer DirInfo(7,2)
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(any,any)
dim shared as integer frontMax = 9000
redim shared as integer frontier(frontMax,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
declare function FrontierDel(ByVal thisOne as integer) as integer
declare sub PutBlocker(ByVal cnt as integer)
declare sub PutMapPF(ByVal ot as integer, ByVal cnt as integer)
declare sub MakeHeatMap(ByVal ot as integer)


'-MAIN--------------------------------------
'-------------------------------------------
randomize TIMER
screenres SCRW,SCRH,32, _ 
			2, _                               'sets application screen page number
            fb.GFX_SHAPED_WINDOW   + _               'enables application standard transparency
            fb.GFX_ALPHA_PRIMITIVES   + _               'enables application standard alpha
            fb.GFX_NO_FRAME
color , rgb(110,110,170)
cls

dim as DBUTTON	validateBtn	=>	DBUTTON(SCRW - 230, SCRH - 400, 200, 80, "VALIDATE")

dim as integer blockerNumber =>		100  
dim as integer treeNumber =>		50   
dim as integer ironOreNumber =>		10   
dim as integer berryBushesNumber =>	10   
dim as integer mushroomsNumber =>	10

dim as integer x1, y1, c1
	
#macro _DRAWBCKG()
	' draw grid
	for i as integer = lBound(map, 1) + 1 to uBound(map, 1)
	    x1 = i*TILEW
	    for j as integer = lBound(map, 2) + 1 to uBound(map, 2)
	        y1 = j*TILEH
	        c1 = Gray
	        select case map(i,j,0)
	            case 1
	            c1 = Green
	            case 2
	            c1 = Red
	            case 3
	            c1 = Blue
	            case 4
	            c1 = Yellow
	        end select
	        line(x1, y1)- step(TILEW - 2, TILEH - 2), c1, BF
	    next j
	next i
	
	' fill map with random objects, and init pathfinding heatmaps for each object
	' initialize map distances for pathfinding....
	for i as integer = lBound(map, 1) to uBound(map, 1)
	    for j as integer = lBound(map, 2) to uBound(map, 2)
	        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(blockerNumber) ' Blocker Tiles
	PutMapPF(1, treeNumber)
	MakeHeatMap(1)
	locate 3,94 : Print "map for all Trees"
	locate 5,94 : Print "<select> a rect to refresh"
#endMacro

sub DrawSubsel(xSel as integer, ySel as integer, wSel as integer, hSel as integer, x1 as integer, y1 as integer)
	for x as integer = xSel to xSel + wSel
	    for y as integer = ySel to ySel + hSel
	        ' clear Tree map
	        map(x,y,1) = 999
	        if map(x,y,0) = 1 then 'OOPS! Tree there!
	            map(x,y,1) = 999
	            FrontierAdd(x,y,0,1)
	        end if
	    next y
	next x
	makeHeatMap(1)
	locate 3,94 : Print "map for all Trees"
	locate 5,94 : Print "<select> a rect to refresh"
	for i as integer = lBound(map, 1) to uBound(map, 1)
	    for j as integer = lBound(map, 2) to uBound(map, 2)
	        var 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
end sub

_DRAWBCKG()

dim as any ptr	mapImg	=> imageCreate(SCRW, SCRH, rgb(255,0,255), 32) 
get (0, 0)-(SCRW - 1, SCRH - 1), mapImg

dim as RECTSELECTOR	rcsel
do
	screenset 0, 1
		cls
		put (0,0), mapImg, pset
		rcsel.DrawRectangleSelector()
		validateBtn.DrawButton()
		'
		if validateBtn._mouseClick then
			cls
			put (0,0), mapImg, pset			
			if rcsel._rectSelection._width<0 then
				rcsel._rectSelection._topLeftCornerX = rcsel._rectSelection._topLeftCornerX + rcsel._rectSelection._width
				rcsel._rectSelection._width = -rcsel._rectSelection._width
			end if
			if rcsel._rectSelection._height<0 then
				rcsel._rectSelection._topLeftCornerY = rcsel._rectSelection._topLeftCornerY + rcsel._rectSelection._height
				rcsel._rectSelection._height = -rcsel._rectSelection._height
			end if
			DrawSubsel(	rcsel._rectSelection._topLeftCornerX\TILEW, _ 
						rcsel._rectSelection._topLeftCornerY\TILEH, _ 
						rcsel._rectSelection._width\TILEW, _ 
						rcsel._rectSelection._height\TILEH, _ 
						x1, _ 
						y1	)
			get (0, 0)-(SCRW - 1, SCRH - 1), mapImg
			validateBtn._mouseClick = FALSE
			rcsel._selectionIsRunning = FALSE
		end if
	screencopy 0, 1
	'
	sleep 15
loop until inkey()=chr(27)

imageDestroy mapImg
getKey()

'-------------------------------------------
'-------------------------------------------FrontierAdd
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
            end if
            bub = bub - 1
        loop until bub < 2
    end if
    return frontHere
end function
'-------------------------------------------FrontierDel
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
'-------------------------------------------PutBlocker
sub PutBlocker(ByVal cnt as integer)
    dim as integer x, y
    for i as integer = 1 to cnt
        x = rnd*(.6*xSize) + 4 : y = rnd*(.6*ySize) + 4
        while map(x,y,0) > 0
            x = rnd*(.6*xSize) + 4 : y = rnd*(.6*ySize) + 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
end sub
'-------------------------------------------PutMapPF
sub PutMapPF(ByVal ot as integer, ByVal cnt as integer)
    dim as integer x, y
    for i as integer = 1 to cnt
        x = rnd*(.8*xSize) + 4 : y = rnd*(.8*ySize) + 4
        while map(x,y,0) > 0
            x = rnd*(.8*xSize) + 4 : y = rnd*(.8*ySize) + 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
'-------------------------------------------MakeHeatMap
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
        '
        ' 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>=lBound(map, 1)) andAlso (i<=uBound(map, 1)) andAlso (j>=lBound(map, 2)) andAlso (j<=uBound(map, 2)) 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
'-------------------------------------------
' 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
'-------------------------------------------
'(eof)
Image
Last edited by Tourist Trap on Dec 13, 2018 14:29, edited 1 time in total.
leopardpm
Posts: 1795
Joined: Feb 28, 2009 20:58

Re: Making heatMaps more Dynamic

Post by leopardpm »

Tourist Trap wrote:It's a pitty that I find it so hard to go throught your style of coding.
I completely apologize for my coding 'style' (or more specifically, 'lack of')..... its almost always some sort of stream-of-consciousness when I code and then I go back to fix things and it all gets muddled up... I end up having to re-write routines after I have the logic figured out so that they then can be readable... totally my fault, sir!
I can't see what is a Fronteer function for instance, and so on).
There isn't a 'Frontier' function - just 2 routines which deal with the Frontier array which is just a sorted list of cells that the flood-fill routine (breadth-first) uses to keep track of where it is.
Here, I finally managed to make some addition to the inital code we started with. I absolutly don't know what you do there in depth. But I added some interactivity. You can select a rectangle on the map, and push the button at the right and refresh the zone. You can cancel also a selection with the button2. It makes it easier to test the first idea we discussed at first.
Cool! Thanks... it works good enough to easily show how such a method will be hard pressed to work correctly, i think.

I haven't gotten around to finishing the routine to re-generate from a deleted node(tree) yet, but it isn't so hard to figure out.
grindstone
Posts: 862
Joined: May 05, 2015 5:35
Location: Germany

Re: Making heatMaps more Dynamic

Post by grindstone »

@leopardpm

A little hint: The Sub/Function declarations in your code are completely needless. A procedure has only to be declared if it is called before it's defined in the source code.
Tourist Trap
Posts: 2958
Joined: Jun 02, 2015 16:24

Re: Making heatMaps more Dynamic

Post by Tourist Trap »

leopardpm wrote:]I completely apologize for my coding 'style' (or more specifically, 'lack of')..... its almost always some sort of stream-of-consciousness when I code and then I go back to fix things and it all gets muddled up... I end up having to re-write routines after I have the logic figured out so that they then can be readable... totally my fault, sir!
No no, I didn't express it well. I'm just sad of not feeling at ease with this style, it is well adapted to implementation of algorithms. I'm also very hampered with the examples exhibited on the other websites we talked about that show examples of pathfinding stuff and so on. I will have to make a big effort if I want to go further I fear!
leopardpm
Posts: 1795
Joined: Feb 28, 2009 20:58

Re: Making heatMaps more Dynamic

Post by leopardpm »

grindstone wrote:@leopardpm

A little hint: The Sub/Function declarations in your code are completely needless. A procedure has only to be declared if it is called before it's defined in the source code.
yeah, i know... I tend to move things around aas I code, and eventually all the declares with go in a header type file and subroutines/functions would be grouped together into separate inc files..... If I were a more disciplined coder than I would start with that type of structure in the first place.
leopardpm
Posts: 1795
Joined: Feb 28, 2009 20:58

Re: Making heatMaps more Dynamic

Post by leopardpm »

getting ready to combine my GOAP routine with an actual map (with Distance Maps/Vector Maps for pathfinding) and just polished up the DistanceMap generator a bit, so this is probably the final version I will use - except that I still need to add the 'dynamic' element to it when removing (or adding) an object from/to the map... been procrastinating on that....

Discovered a bug in the way I was generating the Vector Maps due to the sequence of events I had in making each resource map individually, so remade that section... the routine now also treats all the resources as movement blockers and paths around them... nothing is 'optimized', trying to stay away from both optimizing and graphics due to my tendency to focus on those rabbit-holes instead of the main goal....

Planning on posting a new thread as a tutorial on making a basic GOAP AI for NPC's, for anyone who cares...

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 = 14

'==============================================
type dmapinfo
    as ushort dist
    as ubyte  pntr
    as ubyte  dirVect
end type

type mainmap
    as ubyte Obj
    as dmapinfo DMInfo(1 to 4) '1=tree, 2=iron, 3=bush, 4=mush
end type

dim shared as mainmap map(mapsizeX, mapsizeY)

    ' get Map ready...
    for i as integer = 0 to mapsizeX
        for j as integer = 0 to mapsizeY
            ' clear map objects
            map(i,j).obj = 0
            ' initialize map distances for pathfinding....
            map(i,j).DMInfo(Trees).dist = 999
            map(i,j).DMInfo(IronOre).dist = 999
            map(i,j).DMInfo(BerryBushes).dist = 999
            map(i,j).DMInfo(Mushrooms).dist = 999
        next j
    next i
    
'==============================================
type dinfo
    as byte xAdj
    as byte yAdj
    as byte mCost
end type

dim shared as dinfo DirInfo(7) ' for movement & pathfinding
' directions 0-7
' 7 0 1
' 6 x 2
' 5 4 3
'
' info: xAdj, yAdj, 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

    ' initialize Direction Information Array
    for i as integer = 0 to 7
        read DirInfo(i).xAdj
        read DirInfo(i).yAdj
        read DirInfo(i).mCost
    next i

'==============================================
type frontierPQ
    as ushort Cost
    as ushort x
    as ushort y
    as ushort objNum
end type

dim shared as frontierPQ frontier(2000)
dim shared as integer fPntr

'==============================================

dim shared as integer Remove(1)

type resource
    as ushort health
    as ushort x
    as ushort y
end type
dim shared as resource WorldResource(100, 1 to 4) ' index '0' is how many of that obj type....
dim shared as integer NumOfWR(1 to 4)
'==============================================

' some subroutines....
declare function FrontierAdd(ByVal frontX as integer, ByVal frontY as integer, ByVal frontCost as integer, byval ot as integer, byval treeNum as integer) as integer
function FrontierAdd(ByVal frontX as integer, ByVal frontY as integer, ByVal frontCost as integer, byval ot as integer, byval treeNum as integer) as integer
    ' this function adds a Map location to the Frontier Array for use in generating a Distance Map
    '  ... add it to the end then bubble sort it down...
    dim as integer bub, frontHere
    fPntr = fPntr + 1
    frontHere = fPntr
    frontier(fPntr).Cost = frontCost
    frontier(fPntr).x = frontX
    frontier(fPntr).y = frontY
    frontier(fPntr).objNum = treeNum
    if fPntr > 1 then
        bub = fPntr
        do
            if frontier(bub).cost > frontier(bub-1).cost then
                swap frontier(bub) , frontier(bub-1)
                frontHere = bub - 1
            else
                exit do ' 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 < fPntr
            for i as integer = thisOne to (fPntr-1)
                frontier(i) = frontier(i+1)
            next i
            fPntr = fPntr - 1
        case is = fPntr
            fPntr = fPntr - 1
    end select
    return thisOne
end function

declare sub CreateResources(ByVal ot1 as integer, ByVal ot2 as integer, ByVal ot3 as integer, ByVal ot4 as integer)
sub CreateResources(ByVal ot1 as integer, ByVal ot2 as integer, ByVal ot3 as integer, ByVal ot4 as integer)
    
    dim as integer x, y
    dim as integer ResType(1 to 4)
    ResType(1) = ot1 : ResType(2) = ot2
    ResType(3) = ot3 : ResType(4) = ot4
    for rt as integer = 1 to 4
        if ResType(rt) > 0 then
            NumOfWR(rt) = 0
            for i as integer = 1 to ResType(rt)
                x = rnd * (mapsizeX-2) + 1
                y = rnd * (mapsizeY-2) + 1
                while map(x,y).obj > 0
                    x = rnd * (mapsizeX-2) + 1
                    y = rnd * (mapsizeY-2) + 1
                wend
                
                map(x,y).obj = rt             ' put 1 object(ot) there
                map(x,y).DMInfo(rt).pntr = i
                map(x,y).DMInfo(rt).dist = 0  ' zero out the distance for that object
                ' add it to WorldResource() array for each obj type
                NumOfWR(rt) += 1
                WorldResource(i,rt).x = x
                WorldResource(i,rt).y = y
                WorldResource(i,rt).health = 100
            next i
        end if
    next rt
end sub

declare sub MakeDistanceMaps
sub MakeDistanceMaps
    ' a basic Djistra's Floodfill routine, not optimized at all...
    ' Assumes Frontier hold correct objects....
    '
    dim as integer x, y, i, j, dist, distNew, oldPoint, objPntr
    dim as integer x1, y1
    for ot as integer = 1 to 4
        'make frontier for this ot
        fPntr= 0
        if NumOfWR(ot) > 0 then
            for i = 1 to NumOfWR(ot)
                FrontierAdd(WorldResource(i,ot).x,WorldResource(i,ot).y,0, ot, i)
            next i
        end if

        do
            oldPoint = fPntr
            dist     = frontier(fPntr).cost
            x        = frontier(fPntr).x
            y        = frontier(fPntr).y
            objPntr  = frontier(fPntr).objNum
            
            ' remove point from frontier
            FrontierDel(oldPoint) 'remove current point from frontier
    
            ' 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).xAdj
                j = y+DirInfo(direct).yAdj
                ' make sure within Map bounds and not a Blocker
                if ((i > 0) and (i < (mapsizeX+1))) and ((j > 0) and (j < (mapsizeY+1))) then
                    if (map(i,j).obj = 0  ) then
                        distNew = dist + DirInfo(direct).mCost
                        x1 = i*TILEW
                        y1 = j*TILEH
                        ' if new dist is less than old dist...
                        if map(i,j).DMInfo(ot).dist > distNew then
                            ' if old dist = UNVISITED...
                            if map(i,j).DMInfo(ot).dist = 999 then
                                FrontierAdd(i,j,distNew,ot, objPntr)
                            end if
                            map(i,j).DMInfo(ot).dist    = distNew
                            map(i,j).DMInfo(ot).dirVect = (direct+4) mod 8  ' save flow field info
                            map(i,j).DMInfo(ot).pntr    = objPntr
                        end if
                    end if
                end if
            next direct
        loop until fPntr = 0
    next ot
end sub


' MAIN
    dim as integer x1, y1, c1, clrNew, ot
    screenres SCRW,SCRH,32
    randomize

    CreateResources(8,2,5,1) ' (trees, IronDeposits, bushes, mushrooms)
    MakeDistanceMaps

for ot = 1 to 4
    cls
    for i as integer = 1 to mapsizeX
        x1 = i*TILEW
        for j as integer = 1 to mapsizeY
            y1 = j*TILEH
            c1 = Gray
            clrNew = 255 - (map(i,j).DMInfo(ot).dist/.3)
            if clrNew < 0 then clrNew = 0
            if map(i,j).obj = 0 then
                select case ot
                    case Trees ' distance to nearest tree object (#1)
                        c1 = rgb(0,clrNew,0)
                    case IronOre ' distance to nearest iron ore object (#2)
                        c1 = rgb(clrNew,0,0)
                    case BerryBushes ' distance to nearest Berry Bush Object (#3)
                        c1 = rgb(0,0,clrNew)
                    case Mushrooms ' distance to nearest Mushroom Object (#4)
                        c1 = rgb(clrNew,clrNew,0)
                end select
            else
                select case map(i,j).obj
                    case Trees ' distance to nearest tree object (#1)
                        c1 = Green
                    case IronOre ' istance to nearest iron ore object (#2)
                        c1 = Red
                    case BerryBushes ' distance to nearest Berry Bush Object (#3)
                        c1 = Blue
                    case Mushrooms ' distance to nearest Mushroom Object (#4)
                        c1 = Yellow
                end select
            end if

            line(x1,y1)- step(TILEW-2,TILEH-2),c1,BF
            if map(i,j).obj = 0 then
                'erase distance value box
                line(x1+11,y1+15)- step(24,10), Gray, BF
                'put new distance value in box
                draw string (x1+12,y1+17), str(map(i,j).DMInfo(ot).dist), Blue
            else
                if map(i,j).obj = ot then
                    circle(x1+(TILEW/2)-1,y1+(TILEH/2)-1), 15, c1,,,,f
                    select case ot
                        case IronOre,BerryBushes
                            draw string (x1+17,y1+17), str(map(i,j).DMinfo(ot).pntr), White
                        case else
                            draw string (x1+17,y1+17), str(map(i,j).DMinfo(ot).pntr), Black
                    end select
                        
                end if
                circle(x1+(TILEW/2)-1,y1+(TILEH/2)-1), 13, Black
                circle(x1+(TILEW/2)-1,y1+(TILEH/2)-1), 14, Black
                circle(x1+(TILEW/2)-1,y1+(TILEH/2)-1), 16, Black
                circle(x1+(TILEW/2)-1,y1+(TILEH/2)-1), 17, Black
            end if
        next j
    next i

    locate 3,40 : Print "Distance Map for Object Type #";ot
    locate 4,25 : print "The values shown are the distances from the nearest Object"
    sleep

    cls
    for i as integer = 1 to mapsizeX
        x1 = i*TILEW
        for j as integer = 1 to mapsizeY
            y1 = j*TILEH
            c1 = Gray
            clrNew = 255 - (map(i,j).DMInfo(ot).dist/.3)
            if clrNew < 0 then clrNew = 0
            if map(i,j).obj = 0 then
                select case ot
                    case Trees ' distance to nearest tree object (#1)
                        c1 = rgb(0,clrNew,0)
                    case IronOre ' distance to nearest iron ore object (#2)
                        c1 = rgb(clrNew,0,0)
                    case BerryBushes ' distance to nearest Berry Bush Object (#3)
                        c1 = rgb(0,0,clrNew)
                    case Mushrooms ' distance to nearest Mushroom Object (#4)
                        c1 = rgb(clrNew,clrNew,0)
                end select
            else
                select case map(i,j).obj
                    case Trees ' distance to nearest tree object (#1)
                        c1 = Green
                    case IronOre ' distance to nearest iron ore object (#2)
                        c1 = Red
                    case BerryBushes ' distance to nearest Berry Bush Object (#3)
                        c1 = Blue
                    case Mushrooms ' distance to nearest Mushroom Object (#4)
                        c1 = Yellow
                end select
            end if

            line(x1,y1)- step(TILEW-2,TILEH-2),c1,BF
            if map(i,j).obj = 0 then
                circle(x1+(TILEW/2),y1+(TILEH/2)), 8, White,,,,f
                line(x1+(TILEW/2),y1+(TILEH/2)) - step (DirInfo(map(i,j).DMinfo(ot).dirVect).xAdj*15,DirInfo(map(i,j).DMinfo(ot).dirVect).yAdj*15),White
                draw string (x1+17,y1+17), str(map(i,j).DMinfo(ot).pntr), Black
             else
                if map(i,j).obj = ot then
                    circle(x1+(TILEW/2)-1,y1+(TILEH/2)-1), 15, c1,,,,f
                    select case ot
                        case IronOre, BerryBushes
                            draw string (x1+17,y1+17), str(map(i,j).DMinfo(ot).pntr), White
                        case else
                            draw string (x1+17,y1+17), str(map(i,j).DMinfo(ot).pntr), Black
                    end select
                    
                end if
                circle(x1+(TILEW/2)-1,y1+(TILEH/2)-1), 13, Black
                circle(x1+(TILEW/2)-1,y1+(TILEH/2)-1), 14, Black
                circle(x1+(TILEW/2)-1,y1+(TILEH/2)-1), 16, Black
                circle(x1+(TILEW/2)-1,y1+(TILEH/2)-1), 17, Black
            end if
        next j
    next i
    locate 3,40 : Print  "Flow Field for Object Type #";ot
    locate 4,35 : print "(also showing which Obj is Nearest)"
    sleep
next ot
leopardpm
Posts: 1795
Joined: Feb 28, 2009 20:58

Re: Making heatMaps more Dynamic

Post by leopardpm »

Paul, quick question:

I have been pondering (agonizing) over the use of Flow Fields for my application because you seem so adamant about them. I must be missing some key piece of information. Here is what I understand:

(1) Each 'type' of item will require its own Flow Map for pathing (type = trees, bushes, etc as well as ANYTHING that might be pathed to, including any objects which might be dropped on the ground like weapons, food, any items)
(2) It takes at least 3 bits to store a Flow Vector(8 directions) for each map location
(3) If an item is added/removed from world, then its corresponding Flow Map must be updated.
(4) If ANY movement blocking item (or wall) is added/removed, then ALL Flow Maps must be updated.

Are these things all true?

If so, then I cannot see ONLY using Flow Maps for pathing because: (1) there will be too many items, (2) the blocking updates (#4) might not be so trivial. I do plan on using them for the most obvious items: trees, resource nodes, possibly buildings or special areas.... so maybe 10-15 flow maps total for all these. But I can't see the benefit of having perhaps 100's of flow maps with all the possible maintenance associated, as well as memory usage......would you agree?

actually, for those 10-15 Flow Maps, I will probably just use Distance Maps because I want/need super-fast access to the actual distance without having to 'follow the flow' to generate it. So instead of 3 bits/map location, I will use 1 byte to get a maximum distance of 255 (which should be plenty). And I will have to use A* for anything else that needs pathing.... unless you have ideas
paul doe
Moderator
Posts: 1730
Joined: Jul 25, 2017 17:22
Location: Argentina

Re: Making heatMaps more Dynamic

Post by paul doe »

leopardpm wrote:...
(1) Each 'type' of item will require its own Flow Map for pathing (type = trees, bushes, etc as well as ANYTHING that might be pathed to, including any objects which might be dropped on the ground like weapons, food, any items)
(2) It takes at least 3 bits to store a Flow Vector(8 directions) for each map location
(3) If an item is added/removed from world, then its corresponding Flow Map must be updated.
(4) If ANY movement blocking item (or wall) is added/removed, then ALL Flow Maps must be updated.

Are these things all true?
...
#1: No. In my case for example, I have ONE flow field for anything that is immovable (but not immutable, alas), ONE for anything that is collectable (think items, treasure and such), one for each resource (if appropriate), and so on.
#2: Not necessarily. You can directly store the direction vector (which will make a lot of things easier down the road).
#3: Yes. I already told you how you need to proceed in this case.
#4: Yes. Ditto above.
leopardpm wrote: ...
If so, then I cannot see ONLY using Flow Maps for pathing because: (1) there will be too many items, (2) the blocking updates (#4) might not be so trivial. I do plan on using them for the most obvious items: trees, resource nodes, possibly buildings or special areas.... so maybe 10-15 flow maps total for all these. But I can't see the benefit of having perhaps 100's of flow maps with all the possible maintenance associated, as well as memory usage......would you agree?
...
No, I don't. Time your pathing routines to a good implementation (not just a 'toy' implementation like this one) and you'll be surprised how much of a difference this can make. Of course they use more memory, but so what? Are you coding this on a Commodore 64? If memory is a concern you can fool around with the data representation, but I wouldn't bother as it will make other things more difficult/impossible to implement.
leopardpm wrote: ...
actually, for those 10-15 Flow Maps, I will probably just use Distance Maps because I want/need super-fast access to the actual distance without having to 'follow the flow' to generate it. So instead of 3 bits/map location, I will use 1 byte to get a maximum distance of 255 (which should be plenty). And I will have to use A* for anything else that needs pathing.... unless you have ideas
...
Yes, I gave you several. So, you want to have HUGE maps, and you think that 1 byte to represent distances is 'plenty'? Just how much a cell represents, anyway? Not to mention, if the map is too large/convoluted this will give you troubles (overflow).

A* is fine for ONE agent of size ONE CELL. And that's it. For any other uses (for example an agent of arbitrary size) you need to use something else, such as HAA*. As I told you before, agents need not (and in fact should not) be part of the flow map! You can use steering behaviors to keep units from running into each other (which are a pretty good fit for FF maps), via attractor/repulsor fields to keep them grouped/separated. There are several techniques to achieve this, so you can pick and choose the more appropriate for your tastes.

Of course you'll need to use other pathing routines like A* and Dijkstra's. Flow fields are just another tool on the shack. They're excellent for determining the overall path a massive number of units (think thousands) should take to reach a destination. They're just approximations, but you can indeed use them at a finer resolution if you want.
leopardpm
Posts: 1795
Joined: Feb 28, 2009 20:58

Re: Making heatMaps more Dynamic

Post by leopardpm »

Thanks Paul - I understand better now.

re: Huge map & memory
My past experience (80's) has always had huge memory constraints, so I just naturally think that way. In most cases, I should not worry about memory requirements so much, I realize. But I can see issues possibly down the line... for instance a world of 10k x 10k x 100 'depth' would be 10gb if only 1 byte per cell! for now, i will keep things manageable with 1k x 1k x 10 (10mb) (or smaller) since it's just prototyping (or, a 'toy', as you might say)... should be more than enough room to fully test out the wide-scale effects of things (local --> regional economic information exchange, etc). I said '255' is large enough for a distance value in a Distance map because the maps are used just for local, more precise pathing, not long distance travel which would use a different kind of map representation (basically Hierarchical). I also like things that fit nicely into byte-sized pieces - again, leftovers from early days.
Boromir
Posts: 463
Joined: Apr 30, 2015 19:28
Location: Oklahoma,U.S., Earth,Solar System
Contact:

Re: Making heatMaps more Dynamic

Post by Boromir »

leopardpm wrote: for instance a world of 10k x 10k x 100 'depth' would be 10gb if only 1 byte per cell!
Do you need the whole world in memory at once? You could store a large portion on disc and load and unload as needed based on where agents are populated. It's worked well for my purposes but if your agents are evenly spread out across the map it might not save too much memory.
paul doe
Moderator
Posts: 1730
Joined: Jul 25, 2017 17:22
Location: Argentina

Re: Making heatMaps more Dynamic

Post by paul doe »

leopardpm wrote:...
But I can see issues possibly down the line... for instance a world of 10k x 10k x 100 'depth' would be 10gb if only 1 byte per cell! for now, i will keep things manageable with 1k x 1k x 10 (10mb) (or smaller) since it's just prototyping (or, a 'toy', as you might say)... should be more than enough room to fully test out the wide-scale effects of things (local --> regional economic information exchange, etc)...
The issues you mention are just because you're thinking in terms of an 'array of cells'. As I suggested before, you should not think or lay out the map this way. As Boromir also suggested, you can simply stream portions of the map on-demand. Another thing to consider is to go the extra mile and lay out the map(s) in terms of nodes of different sizes (ranging from entire regions of the world down to a house, for example), and to use better data structures (priority queues and spatial hashes, say). That way, you can have a multi-tiered path finder that can query the entire world if you want. And you don't waste any memory (if that is your main concern) in cells that won't get visited, ever. Have a look at this:

The continuous world of Dungeon Siege

A little old, but very cool and influential post-mortem. The game itself was crap, granted, but the technology behind it was quite remarkable (this and their Entity-Component-System model set the standard for decades to come).
leopardpm wrote:...I said '255' is large enough for a distance value in a Distance map because the maps are used just for local, more precise pathing, not long distance travel which would use a different kind of map representation (basically Hierarchical). I also like things that fit nicely into byte-sized pieces - again, leftovers from early days...
Consider that just a 256*256 map (which is quite manageable) has 65536 nodes. If the map has lots of terrain and stuff (the paths tend to get very convoluted) it is well within the realm of possibility to have overflow issues, see? What's wrong with a plain, simple 32-bit integer?
leopardpm
Posts: 1795
Joined: Feb 28, 2009 20:58

Re: Making heatMaps more Dynamic

Post by leopardpm »

Boromir wrote:
leopardpm wrote: for instance a world of 10k x 10k x 100 'depth' would be 10gb if only 1 byte per cell!
Do you need the whole world in memory at once? You could store a large portion on disc and load and unload as needed based on where agents are populated. It's worked well for my purposes but if your agents are evenly spread out across the map it might not save too much memory.
I have considered streaming the world (ala minecraft style), but the issue is with AI agents always being 'active', whether or not near a player.... a village of AI could be existing on the other side of the World and all those AI would need map access... I do not like the idea of loading/unloading maps because of slower disk access... but it can be hidden pretty well with the right routines, etc.
Post Reply