## The island - An RTS game

User projects written in or related to FreeBASIC.
ITomi
Posts: 113
Joined: Jul 31, 2015 11:23
Location: Hungary

### Re: The island - An RTS game

Hello everybody!

It's me again. I have started working with this project again (I was very busy, but I didn't forget it), and I've already finished it.
But I have to rewrite the algorithm that move the units.
My question is that is it possible to redimensioning a two dimensional array and using it in a type?
I would like store the XY coordinates of the units in a particular array, when it moving on its own path.
MrSwiss
Posts: 2968
Joined: Jun 02, 2013 9:27
Location: Switzerland

### Re: The island - An RTS game

Well, the way I understand your question:
1) you have a Type with coordinates: x and y
2) you have a array of a Type (another, already defined)
then I'd do it as follows:

Code: Select all

`Type coord    As Long(Single opt.) x, yEnd TypeType MyType    As coord xypos    ...    ...    ...End Type' Declare the array of MyType ... etc.`
Using above method, there is no need to resize the array, holding e.g. something like 'Player'.
On the other hand, you could use a array (any shape and size) inside a Type too ...

dodicat
Posts: 5608
Joined: Jan 10, 2006 20:30
Location: Scotland

### Re: The island - An RTS game

If you have several paths to store then, following on from Mr Swiss's suggestion:

Code: Select all

`type XY    as long x,yend typedeclare sub circulate(p() as XY) 'optionaltype path    as XY coord(any)end typedim as long tracknum=15redim as path track()redim track(1 to tracknum)for n as long=1 to tracknum    dim as long num=8+rnd*16    redim (track(n).coord)(num)   'create a random number of points per tracknext nfor n as long=1 to tracknum    for m as long=0 to  ubound(track(n).coord)    track(n).coord(m)=type(rnd*800,rnd*600) 'set random on-screen XY positions for each tracknext mnext nfor n as long=1 to tracknum    circulate(track(n).coord())'sort the nodes by angles, giving a more circular spread                               ' of the random points    next nscreen 19dim as long counter,mfor n as long=1 to tracknum     counter=0    for m =0 to ubound(track(n).coord)        counter+=1        if m=0 then             pset(track(n).coord(m).x,track(n).coord(m).y),n        else            line  -(track(n).coord(m).x,track(n).coord(m).y),n            end if    next m    'close the polygon track    line -(track(n).coord(0).x,track(n).coord(0).y),nprint "Track ";n; "  of ";tracknum;" with ";counter; " nodes "printprint "press a key"sleepclsnext nprint "Done"sleepsub circulate(p() as XY) #macro Circlesort()  '  bubblesort by angleFor p1 as long  = lbound(p) To ubound(p)-1    For p2 as long  = p1 + 1 To ubound(p)        if atan2(p(p1).y-c.y,p(p1).x-c.x)< atan2(p(p2).y-c.y,p(p2).x-c.x) then            swap p(p1),p(p2)            end if         Next p2    Next p1 #endmacro dim as XY C '--centroid of points dim as long counter for n as long=lbound(p) to ubound(p)     counter+=1     c.x+=p(n).x     c.y+=p(n).y next n c.x=c.x/counter c.y=c.y/counter CircleSort()end sub `
BasicCoder2
Posts: 3344
Joined: Jan 01, 2009 7:03

### Re: The island - An RTS game

Not sure if this is the same issue I had with each agent generating its own path which had a variable length for each path generation and for each agent ?
I just gave the path array enough steps for a maximum number limit. This meant most of the path steps were not used and a waste of memory.
Thus in the example below every agent had an array of a fixed 3000 steps even if they were not all used.

Code: Select all

`screenres 640,480,32dim shared as integer dx,dytype APOINT    as integer x    as integer yend typetype PATH    as APOINT  path(0 to 3000)   'up to 3000 steps <-- HOW TO GIVE EACH PATH TYPE A VARIABLE path LENGTH    as integer pathLength    as ulong   pathColorend typedim shared as PATH paths(0 to 3)  'four paths of up to 3000 steps'make four random pathsfor i as integer = 0 to 3   'for each path    paths(i).pathColor = rgb(int(rnd(1)*256),int(rnd(1)*256),int(rnd(1)*256)) 'select a color    paths(i).pathLength = int(rnd(1)*1500)+1000 'choose a length 1500 to 2500    paths(i).path(0).x = int(rnd(1)*640)  'set starting point    paths(i).path(0).y = int(rnd(1)*480)    for j as integer = 1 to paths(i).pathLength 'make random moves up to path length        dx = int(rnd(1)*3)-1        dy = int(rnd(1)*3)-1        paths(i).path(j).x = paths(i).path(j-1).x + dx        paths(i).path(j).y = paths(i).path(j-1).y + dy    next jnext i'now draw themfor i as integer = 0 to 3    for j as integer = 0 to paths(i).pathLength-1        pset ( paths(i).path(j).x, paths(i).path(j).y ),paths(i).pathColor    next jnext isleep`
D.J.Peters
Posts: 7659
Joined: May 28, 2005 3:28

### Re: The island - An RTS game

Code: Select all

`screenres 640,480,32dim shared as integer dx,dytype APOINT  as integer x  as integer yend typetype PATH  declare sub addPoint(x as integer,y as integer)  declare sub addPoint(a as APOINT)  declare function getPoint(index as integer) as APOINT  as APOINT  ptr Points  as integer nPoints  as integer pathLength  as ulong   pathColorend typesub PATH.addPoint(item as APOINT)  dim as integer index=nPoints : nPoints+=1  Points = reallocate(Points,nPoints*sizeof(APOINT))  Points[index]=itemend sub  sub PATH.addPoint(x as integer,y as integer)  dim as integer index=nPoints : nPoints+=1  Points = reallocate(Points,nPoints*sizeof(APOINT))  Points[index].x=x  Points[index].y=yend sub  function PATH.getPoint(index as integer) as APOINT  if index<0 or index>=nPoints then     screen 0 : print "fatal error: index out of bounds !"    beep : sleep: end 1  end if  return Points[index]end functiondim as PATH aPath' add a point by x,yaPath.addPoint(10,20)' or by temporary typeaPath.addPoint(type<aPoint>(20,20))' or by copy of an pointdim as APOINT testtest.x=40 : test.y=50aPath.addPoint(test)' access x,y directly via pointer []for i as integer=0 to aPath.nPoints-1  print aPath.points[i].x,aPath.points[i].ynextprint' or access x,y indirectly fia function ()for i as integer=0 to aPath.nPoints-1  print aPath.getPoint(i).x,aPath.getPoint(i).ynextprint' or by copy of an item APOINT for i as integer=0 to aPath.nPoints-1  dim as APOINT p = aPath.getPoint(i)  print p.x,p.ynextsleep`
BasicCoder2
Posts: 3344
Joined: Jan 01, 2009 7:03

### Re: The island - An RTS game

Thanks Joshy. Here I have applied your version to my example.

Code: Select all

`screenres 640,480,32dim shared as integer dx,dytype POINT2D    as integer x    as integer yend typetype PATH  declare sub addPoint(x as integer,y as integer)  declare sub addPoint(a as POINT2D)  declare function getPoint(index as integer) as POINT2D  as POINT2D  ptr Points  as integer nPoints  as integer pathLength  as ulong   pathColorend typesub PATH.addPoint(item as POINT2D)  dim as integer index=nPoints : nPoints+=1  Points = reallocate(Points,nPoints*sizeof(POINT2D))  Points[index]=itemend sub  sub PATH.addPoint(x as integer,y as integer)  dim as integer index=nPoints : nPoints+=1  Points = reallocate(Points,nPoints*sizeof(POINT2D))  Points[index].x=x  Points[index].y=yend sub  function PATH.getPoint(index as integer) as POINT2D  if index<0 or index>=nPoints then     screen 0 : print " fatal error: index out of bounds !"    beep : sleep: end 1  end if  return Points[index]end functiondim as PATH aPath(0 to 4)dim as POINT2D pt2d  'general purpose POINT2D type'create pathsfor i as integer = 0 to 3    aPath(i).pathColor = rgb(int(rnd(1)*256),int(rnd(1)*256),int(rnd(1)*256)) 'select a color    aPath(i).pathLength = int(rnd(1)*1500)+1000 'choose a length 1500 to 2500    pt2d.x =  int(rnd(1)*640)  'set starting point    pt2d.y =  int(rnd(1)*480)    aPath(i).addPoint(pt2d)    for j as integer = 1 to aPath(i).pathLength 'make random moves up to path length        pt2d.x = pt2d.x + int(rnd(1)*3)-1        pt2d.y = pt2d.y + int(rnd(1)*3)-1        aPath(i).addPoint(pt2d)    next jnext i'draw pathsfor i as integer = 0 to 3    for j as integer=0 to aPath(i).nPoints-1        pt2d = aPath(i).getPoint(j)        pset( pt2d.x,pt2d.y ),aPath(i).pathColor    nextnext isleep`
D.J.Peters
Posts: 7659
Joined: May 28, 2005 3:28

### Re: The island - An RTS game

BasicCoder2 here are a more faster version and I added the missing destructor.

If you dim a PATH it reservers the first 8 points later

if you add the 9' point it resize the array/pointer to 16

if you add the 17' point it resize the array to 32

if you add the 33' point it resize the array to 64

if you add the 65' point it resize the array to 128

and so on ...

It's much faster than reallocate it every time you add one point

Joshy

Code: Select all

`screenres 640,480,32dim shared as integer dx,dytype POINT2D    as integer x    as integer yend typetype PATH  declare destructor  declare constructor  declare sub addPoint(x as integer,y as integer)  declare sub addPoint(a as POINT2D)  declare function getPoint(index as integer) as POINT2D  as POINT2D  ptr Points  as integer nPoints,MAX_POINTS  as integer pathLength  as ulong   pathColorend typedestructor PATH  if Points then deallocate Pointsend destructorconstructor PATH  MAX_POINTS=8  Points = reallocate(Points,MAX_POINTS*sizeof(POINT2D))end constructorsub PATH.addPoint(item as POINT2D)  dim as integer index=nPoints : nPoints+=1  if nPoints>MAX_POINTS then    MAX_POINTS shl=1 : Points = reallocate(Points,MAX_POINTS*sizeof(POINT2D))  end if    Points[index]=itemend sub sub PATH.addPoint(x as integer,y as integer)  dim as integer index=nPoints : nPoints+=1  if nPoints>MAX_POINTS then    MAX_POINTS shl=1 : Points = reallocate(Points,MAX_POINTS*sizeof(POINT2D))  end if  Points[index].x=x  Points[index].y=yend sub function PATH.getPoint(index as integer) as POINT2D  if index<0 or index>=nPoints then    screen 0 : print " fatal error: index out of bounds !"    beep : sleep: end 1  end if  return Points[index]end functiondim as PATH aPath(0 to 4)dim as POINT2D pt2d  'general purpose POINT2D type'create pathsfor i as integer = 0 to 3    aPath(i).pathColor = rgb(int(rnd(1)*256),int(rnd(1)*256),int(rnd(1)*256)) 'select a color    aPath(i).pathLength = int(rnd(1)*1500)+1000 'choose a length 1500 to 2500    pt2d.x =  int(rnd(1)*640)  'set starting point    pt2d.y =  int(rnd(1)*480)    aPath(i).addPoint(pt2d)    for j as integer = 1 to aPath(i).pathLength 'make random moves up to path length        pt2d.x += int(rnd(1)*3)-1        pt2d.y += int(rnd(1)*3)-1        aPath(i).addPoint(pt2d)    next jnext i'draw pathsfor i as integer = 0 to 3    for j as integer=0 to aPath(i).nPoints-1        pt2d = aPath(i).getPoint(j)        pset( pt2d.x,pt2d.y ),aPath(i).pathColor    nextnext isleep`
ITomi
Posts: 113
Joined: Jul 31, 2015 11:23
Location: Hungary

### Re: The island - An RTS game

Thanks, boys!
I've picked some code from the game that is focusing into the pathfinding. But something is wrong with it, when the unit collide with others. Here is the code:

Code: Select all

`#include "fbgfx.bi"Using FBrandomizeconst sw=640 : const sh=480const unitspeed=1const pi As Double=3.1415926535897932type units    as integer xplace,yplace,endx,endy,numofways,actnumofways    as ubyte exists,marked    as string whatdoesend typetype things    as integer xplace,yplace    as ubyte exists,nameend typedim shared numofunits as integer=2dim shared a_unit(numofunits) as unitsdim shared numofthings as integer=0dim shared thing(numofthings) as thingsdim shared goodcell(0,2) as integerdim shared path(0,2) as integerfunction pointdist(x1 as integer,y1 as integer,x2 as integer,y2 as integer) as double    return sqr((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1))end functionfunction emptyspace(herex as integer, herey as integer, spacew as integer, spaceh as integer) as ubyte    for i as integer=0 to numofthings-1        if thing(i).xplace-5<herex-5+spacew and thing(i).xplace-5+10>herex-5 and thing(i).yplace-5<herey-5+spaceh and 10+thing(i).yplace-5>herey-5 then return 0    next i    return 1end functionfunction not_previouscell(cellx as integer, celly as integer, cellnum as integer) as ubyte    if cellnum=0 then        return 1    else        for i as integer=0 to cellnum-1            if goodcell(i,0)=cellx and goodcell(i,1)=celly then return 0        next i    end if    return 1end functionfunction freeneighborcell(vrx as integer, vry as integer, vjordb as integer) as ubyte    dim as ubyte freenumbers    freenumbers=0    if emptyspace(vrx+5,vry,10,10)=1 and not_previouscell(vrx+5,vry,vjordb)=1 then freenumbers+=1    if emptyspace(vrx-5,vry,10,10)=1 and not_previouscell(vrx-5,vry,vjordb)=1 then freenumbers+=1    if emptyspace(vrx,vry+5,10,10)=1 and not_previouscell(vrx,vry+5,vjordb)=1 then freenumbers+=1    if emptyspace(vrx,vry-5,10,10)=1 and not_previouscell(vrx,vry-5,vjordb)=1 then freenumbers+=1    return freenumbersend functionsub obstacles()    for i as ubyte=0 to 10        dim as ubyte xpl,ypl        do            xpl=int(rnd*sw)+1 : ypl=int(rnd*sh)+1        loop until emptyspace(xpl,ypl,10,10)=1        thing(numofthings).exists=1        if int(rnd*2)<1 then            thing(numofthings).name=0        else            thing(numofthings).name=1        end if        thing(numofthings).xplace=xpl : thing(numofthings).yplace=ypl        numofthings+=1 : redim preserve thing(numofthings)    next iend subsub mouseclick()    dim as integer mx,my,mbutton,mouse    mouse=getmouse(mx,my,,mbutton)    if mouse=0 then        if (mbutton and 1) then            for i as integer=0 to numofunits-1                if pointdist(mx,my,a_unit(i).xplace,a_unit(i).yplace)<=10 then                    if a_unit(i).marked=0 then                        a_unit(i).marked=1                    else                        a_unit(i).marked=0                    end if                end if            next i        elseif (mbutton and 2) then            for i as integer=0 to numofunits-1                if a_unit(i).marked=1 then                    a_unit(i).endx=mx : a_unit(i).endy=my                    a_unit(i).whatdoes="go"                end if            next i        end if    end ifend subsub pathfinding(t as integer)    dim as ubyte endofpf,gnum,ways    dim as integer checkx,checky,goodcellnum,nearestx,nearesty    dim as integer goodnextpl(0,2)    endofpf=0 : goodcellnum=0 : ways=0    checkx=a_unit(t).xplace: checky=a_unit(t).yplace    do        gnum=0        if emptyspace(checkx+5,checky,10,10)=1 and freeneighborcell(checkx+5,checky,goodcellnum)>0 and not_previouscell(checkx+5,checky,goodcellnum)=1 then            goodnextpl(gnum,0)=checkx+5 : goodnextpl(gnum,1)=checky : gnum+=1 : redim preserve goodnextpl(gnum,2)        end if        if emptyspace(checkx-5,checky,10,10)=1 and freeneighborcell(checkx-5,checky,goodcellnum)>0 and not_previouscell(checkx-5,checky,goodcellnum)=1 then            goodnextpl(gnum,0)=checkx-5 : goodnextpl(gnum,1)=checky : gnum+=1 : redim preserve goodnextpl(gnum,2)        end if        if emptyspace(checkx,checky+5,10,10)=1 and freeneighborcell(checkx,checky+5,goodcellnum)>0 and not_previouscell(checkx,checky+5,goodcellnum)=1 then            goodnextpl(gnum,0)=checkx : goodnextpl(gnum,1)=checky+5 : gnum+=1 : redim preserve goodnextpl(gnum,2)        end if        if emptyspace(checkx,checky-5,10,10)=1 and freeneighborcell(checkx,checky-5,goodcellnum)>0 and not_previouscell(checkx,checky-5,goodcellnum)=1 then            goodnextpl(gnum,0)=checkx : goodnextpl(gnum,1)=checky-5 : gnum+=1 : redim preserve goodnextpl(gnum,2)        end if        if gnum>0 then            nearestx=goodnextpl(0,0) : nearesty=goodnextpl(0,1)            for i as ubyte=0 to gnum-1                if pointdist(goodnextpl(i,0),goodnextpl(i,1),a_unit(t).endx,a_unit(t).endy)<pointdist(nearestx,nearesty,a_unit(t).endx,a_unit(t).endy) then                    nearestx=goodnextpl(i,0) : nearesty=goodnextpl(i,1)                end if            next i            goodcell(goodcellnum,0)=nearestx : goodcell(goodcellnum,1)=nearesty : goodcellnum+=1 : redim preserve goodcell(goodcellnum,2)            checkx=nearestx : checky=nearesty : ways+=1            if checkx>=a_unit(t).endx-5 and checkx<=a_unit(t).endx+5 and checky>=a_unit(t).endy-5 and checky<=a_unit(t).endy+5 then endofpf=1        else            endofpf=1        end if    loop until endofpf=1 or ways>10    for i as integer=0 to goodcellnum-1        path(i,0)=goodcell(i,0) : path(i,1)=goodcell(i,1) : redim preserve path(i,2)    next i    a_unit(t).numofways=goodcellnum : a_unit(t).actnumofways=0 : a_unit(t).whatdoes="avoid"end subsub unitstate()    dim as integer nextx,nexty    for i as integer=0 to numofunits-1    if a_unit(i).exists=1 then        select case a_unit(i).whatdoes        case "go"            if a_unit(i).endx<=a_unit(i).xplace-unitspeed then                    nextx=a_unit(i).xplace-unitspeed            elseif a_unit(i).endx>=a_unit(i).xplace+unitspeed then                    nextx=a_unit(i).xplace+unitspeed            else                    nextx=a_unit(i).xplace            end if            if a_unit(i).endy<=a_unit(i).yplace-unitspeed then                    nexty=a_unit(i).yplace-unitspeed            elseif a_unit(i).endy>=a_unit(i).yplace+unitspeed then                    nexty=a_unit(i).yplace+unitspeed            else                    nexty=a_unit(i).yplace            end if            if pointdist(a_unit(i).xplace,a_unit(i).yplace,a_unit(i).endx,a_unit(i).endy)<=unitspeed then                a_unit(i).whatdoes="none"            else                if emptyspace(nextx,nexty,10,10)=1 then                    a_unit(i).xplace=nextx : a_unit(i).yplace=nexty                else                    pathfinding(i)                end if            end if        case "avoid"            if pointdist(a_unit(i).xplace,a_unit(i).yplace,path(a_unit(i).actnumofways,0),path(a_unit(i).actnumofways,1))<=unitspeed then                if a_unit(i).actnumofways<a_unit(i).numofways-1 then                    a_unit(i).actnumofways+=1                else                    if pointdist(a_unit(i).xplace,a_unit(i).yplace,a_unit(i).endx,a_unit(i).endy)<=unitspeed then                        a_unit(i).whatdoes="none"                    else                        a_unit(i).whatdoes="go"                    end if                end if            else                if path(a_unit(i).actnumofways,0)<=a_unit(i).xplace-unitspeed then                    nextx=a_unit(i).xplace-unitspeed                elseif path(a_unit(i).actnumofways,0)>=a_unit(i).xplace+unitspeed then                    nextx=a_unit(i).xplace+unitspeed                else                    nextx=a_unit(i).xplace                end if                if path(a_unit(i).actnumofways,1)<=a_unit(i).yplace-unitspeed then                    nexty=a_unit(i).yplace-unitspeed                elseif path(a_unit(i).actnumofways,1)>=a_unit(i).yplace+unitspeed then                    nexty=a_unit(i).yplace+unitspeed                else                    nexty=a_unit(i).yplace                end if                if emptyspace(nextx,nexty,10,10)=1 then                    a_unit(i).xplace=nextx : a_unit(i).yplace=nexty                else                    pathfinding(i)                end if            end if        end select        circle (a_unit(i).xplace,a_unit(i).yplace),10        if a_unit(i).marked=1 then draw string (a_unit(i).xplace,a_unit(i).yplace),a_unit(i).whatdoes    end if    next iend subsub drawingofthings()    for i as integer=0 to numofthings-1        if thing(i).exists=1 then            circle (thing(i).xplace,thing(i).yplace),10            if thing(i).name=0 then                draw string (thing(i).xplace,thing(i).yplace),"TREE"            else                draw string (thing(i).xplace,thing(i).yplace),"STONE"            end if        end if    next iend subscreenres sw,sh,32a_unit(0).exists=1 : a_unit(0).whatdoes="none" : a_unit(0).marked=0a_unit(0).xplace=100 : a_unit(0).yplace=100obstacles()do    screenlock    cls        mouseclick()    unitstate()    drawingofthings()        screenunlock    sleep 10loop until multikey(sc_Q)`
leopardpm
Posts: 1788
Joined: Feb 28, 2009 20:58

### Re: The island - An RTS game

strange... very strange.... first off, I don't see how you are storing your map - are you just using the screen pixels or do you have some sort of map representation somewhere?

If you are just using screen pixels, then you are making things much more complicated then they need to be.... for instance, the circles "stone" and "tree" span across many pixels and to check for a good path, then it will have to check all those pixels - it looks like you check at a certain distance (from the center of the agent?), looking for set pixels... this might miss the thin outline of the circle.... just a quick guess...

why dont you have some sort of grid map, even if it is smaller than the objects, it will still be 10 times easier to check (for instance, even if you have a tiny grid, 2 x 2 pixels each, then each check is the equivalent of check 4 pixels the current way...1/4 the work)

will look harder at the code

ok, I see you store the locations of each 'thing' then when checking if can move it tests for overlapping rectangles(squares actually in this case)...

here is your function to case to see if there is a collison with a thing:

Code: Select all

`function emptyspace(herex as integer, herey as integer, spacew as integer, spaceh as integer) as ubyte    for i as integer=0 to numofthings-1        if thing(i).xplace-5<herex-5+spacew and thing(i).xplace-5+10>herex-5 and thing(i).yplace-5<herey-5+spaceh and 10+thing(i).yplace-5>herey-5 then return 0    next i    return 1end function`

notice how you build in the +5 and -5 ? well, you do it again when you call the function:

Code: Select all

`function freeneighborcell(vrx as integer, vry as integer, vjordb as integer) as ubyte    dim as ubyte freenumbers    freenumbers=0    if emptyspace(vrx+5,vry,10,10)=1 and not_previouscell(vrx+5,vry,vjordb)=1 then freenumbers+=1    if emptyspace(vrx-5,vry,10,10)=1 and not_previouscell(vrx-5,vry,vjordb)=1 then freenumbers+=1    if emptyspace(vrx,vry+5,10,10)=1 and not_previouscell(vrx,vry+5,vjordb)=1 then freenumbers+=1    if emptyspace(vrx,vry-5,10,10)=1 and not_previouscell(vrx,vry-5,vjordb)=1 then freenumbers+=1    return freenumbersend function`

plus, you are saying that each thing has a width and height of 10.... but you check as if they are 11 tall and wide (x-5 to x+5 is 11 units... x-4 to x+5 is 10 units....)

the code is confusing to me, so I am not sure if this is part of the problem, also it looks like you are checking only 4 directions... what about diagonal? I can't tell if diagonal movement is allowed, but it looks like it when I run the program.... crashes though when hits something

I 'kinda' see where this method of keeping track of the height and width of each object could work... but it does make it harder to do things.... is there some reason you want basically a pixel level map?
ITomi
Posts: 113
Joined: Jul 31, 2015 11:23
Location: Hungary

### Re: The island - An RTS game

Hello Leopardm!

In this code I just use screen coordinates. Every obstacles and the unit are a circle with 10 pixels diameter.
The diagonal movement is not allowed.
When you click with the mouse, the unit is moving there, but if collide, it's try to find an own path: it checks its environment, which is the free, square spaces, in same dimension.
If find one, check environment of that, and so on. Always search for the nearest square to the destination, but this may not that cell which is already included in the path yet.
The path is completed in this way.
leopardpm
Posts: 1788
Joined: Feb 28, 2009 20:58

### Re: The island - An RTS game

well, in any case, the problem is in the collision check, obviously.... if you are just checking your pathfinding code, then make it easy and have the moving circle just be 1 pixel (a dot)... then check the pixels in each direction to see if it is black of anything else... he can only move to a black dot. That way you are just checking how your pathfind works without having to try to figure out the corners of the squares (each side 10 pixels) to see if collision... which isn't currently working.
ITomi
Posts: 113
Joined: Jul 31, 2015 11:23
Location: Hungary

### Re: The island - An RTS game

Maybe I found the mistake in the code?
Experimentally I wrote separately a piece of code from the main code, that focusing to filling up a two dimensional array with a loop, and it proved bad: the Windows hang out because of that.
This is the little program:

Code: Select all

`#include "fbgfx.bi"Using FBrandomizeconst sw=640 : const sh=480dim shared numofcells as integer=0dim shared path(numofcells,2) as integerscreenres sw,sh,32for i as integer=0 to 10    rem BAD! path(i,0)=int(rnd*10)+1 : path(i,1)=int(rnd*10)+1 : redim preserve path(i,2)    rem GOOD:    path(numofcells,0)=int(rnd*10)+1 : path(numofcells,1)=int(rnd*10)+1 : numofcells+=1 : redim preserve path(numofcells,2)next idim as integer yplaceyplace=10for i as integer=0 to 10    draw string (10,yplace),str(path(i,0))+":"+str(path(i,1))    yplace+=10next idoloop until multikey(sc_Q)`

And this is the piece of code from the main program, from the pathfinding() function:

Code: Select all

`for i as integer=0 to goodcellnum-1        path(i,0)=goodcell(i,0) : path(i,1)=goodcell(i,1) : redim preserve path(i,2)    next i`

So, the error in using of loop variable?
leopardpm
Posts: 1788
Joined: Feb 28, 2009 20:58

### Re: The island - An RTS game

ITomi wrote:So, the error in using of loop variable?

that particular problem is that you are trying to access an array with 'out of dimension' indexes BEFORE you re-dimension it.

Code: Select all

`rem BAD:    path(i,0)=int(rnd*10)+1 : path(i,1)=int(rnd*10)+1 : redim preserve path(i,2)    rem GOOD:    path(numofcells,0)=int(rnd*10)+1 : path(numofcells,1)=int(rnd*10)+1 : numofcells+=1 : redim preserve path(numofcells,2)`

notice you INC 'numofcells', then redim it, THEN use it on the next loop in the GOOD code
in the BAD code you INC 'numofcells', then you attempt to use it, THEN you REDIM it....

This whole process seems to me to be very over complicated to an otherwise simple task... if you really, really, really have your heart set on continually REDIMming your array, then first get it all working with an extra large set array dimension (like BasicCoder suggested above), THEN alter that code to redimension when necessary only.

even so, here are the 'notes' in my help file regarding REDIM:
NOTES:

[b]ReDim Preserve may not work as expected in all cases:[/b]

Preserve's current behavior is to keep the original data contiguous in memory, and only expand or truncate the size of the memory.
Its behavior (with a single dimension) is well-defined only when the upper bound is changed. If the lower bound is changed, the current result is that the data is in effect shifted to start at the new lower bound.
With multiple dimensions, only the upper bound of only the first dimension may be safely increased. If the first dimension is reduced, the existing mappable data may be lost. If lower-order dimensions are resized at all, the effects can be hard to predict.

ReDim cannot be used on fixed-size arrays - i.e. arrays with constant bounds made with Dim. This includes arrays contained in UDTs (user-defined Types), because currently only fixed-size arrays are supported in UDTs. This also includes fixed-length arrays passed as parameters in a function. FreeBASIC cannot prevent you trying this at compile-time, but the results at run-time will be undefined.

Using ReDim within a member procedure with an array that contains an instance of the object class is undefined, and will [hopefully] result in horrible crashes.

seems too sketchy to me to be used reliably and in all cases... what is your pressing desire to keep allocated memory exactly optimal? The program will ALWAYS need more memory when figuring out a path - is memory so precious that it is needed elsewhere, when not pathfinding? This fixation on perfect memory usage is distracting you in your ultimate goal and the only real and tangible effect on the output will be to slow it down... not a positive.

Can you estimate what the longest possible path will be? Do some tests in your environment, keeping track of 'path length' and determine what would be a safe value to pre-DIMension the path node array - also put into an 'out of bounds' error check before accessing the array to let you know of possible issues....

ALSO, notice that you are only generating ONE path, not keeping track of multiple path attempts (which is what A-STAR does). This means two things: (1) the path generated will very rarely be the shortest path, (2) there is no actual need to keep the found path in an array at all! Just need to save the direction of the path to the next node IN THE NODE itself. What I mean is, if you have a 1000 x 1000 map, with each having:

Code: Select all

`type CELL   as integer Contains       ' whatever is in this cell...   as ubyte NextPathNode     ' path direction to the next node in the path (only actually needs 2 bits to describe one of 4 possible directions)end typeDim WorldMap(1000,1000) as CELL`

...then you have no need for any of this REDIM stuff, nor do you have to maintain a path array at all! You don't even have to clear out all the NextPathNodes in all the cells before making the path because the only ones that will be checked can be cleared as you go...

PROs: infallible, speedy, understandable
CONS: non-optimal memory usage

ANOTHER THOUGHT just occurred to me... your path array only gets larger, never smaller except initially when resetting it. Why not just use a string for your path since they are dynamically allocated internally for you? Then just let FB handle all the REDIM stuff internally.

So, how would you use a string to store the path? Just encode it however you want to store the direction of the next node:

Code: Select all

`dim shared as string * 1 Dir_Up    = "W"dim shared as string * 1 Dir_Down  = "S"dim shared as string * 1 Dir_Left  = "A"dim shared as string * 1 Dir_Right = "D"dim shared as string Path = ""function FindPath(startx as integer, starty as integer,endz as integer, endy as integer) as integer    dim as integer direction, PathLength = 0, curX = startX, curY = startY        ' reset the Path to empty    Path = ""        while curX <> endX and curY <> endY        ' now find the direction to the next node here...        '...        '...        '...                ' once the direction is found, now add it to the Path        select case direction            case 1 : Path = Path + Dir_Up            case 2 : Path = Path + Dir_Down            case 3 : Path = Path + Dir_Left            case 4 : Path = Path + Dir_Right        end select        PathLength += 1    wend    return PathLengthend function`

don't know why I am obsessed with this, BUT...

If you REALLY wanted to conserve memory, then encode the path with RLE. For instance, multiple movements in the same direction would have the number of moves after the direction:

Code: Select all

`non-RLE encoded path string:"WAAAAWWAAWRRRRWRRWWWWRWWWWWRRRRRRRRR"RLE encoded path string:"WA4W2A2WR4WR2W4RW5R9"`
just sayin', for even more 'optimal' memory usage... I would also incorporated diagonal moves, only makes sense in most cases...
ITomi
Posts: 113
Joined: Jul 31, 2015 11:23
Location: Hungary

### Re: The island - An RTS game

Huhhh, thanks, Leopardpm, for your helping words. Using a string to store a path is an interesting idea: I think, it's easyest to assign to a type than an array. I try to build in your suggestions into my program.
Really, only the good pathfinding that miss from my game, but I hope, now it may be done. It's not easy for a "green" programmer as me, but the good advices give many helps. :-)
leopardpm
Posts: 1788
Joined: Feb 28, 2009 20:58

### Re: The island - An RTS game

It's not easy for a "green" programmer as me
you are doing just fine, we all learn each day

ITomi wrote:Really, only the good pathfinding that miss from my game, but I hope, now it may be done.
then you need to focus on A* pathfinding - the routine you use in these past examples will end up with agents doing all manner of annoying things - like getting trapped. And their paths will be extremely non-optimal and not look realistic at all. Search the forums for A* and pathfinding, BasicCoder and I did extensive research into pathfinding and posted some A* routines as well as others... you can follow along our thoughts, trials, and tribulations.... its a fun journey!

also go through Amit Patels website on game writing - VERY good!
Here are links to various sub-sections:

A-STAR: http://www.redblobgames.com/pathfinding/a-star/introduction.html
GENERAL GAME PROGRAMMING: http://www-cs-students.stanford.edu/~amitp/gameprog.html

did you see the posts on this thread about Heat Map pathfinding? You seemed to be gone but me and BasicCoder posted about 3 pages of posts here in this thread.... I just re-read them tonight and we did good fleshing some things out. It will help save alot of time pathfinding for many different instances with many units pathing to various places: trees, Mining, Building Structures, etc. Even enemy avoidance or attacking can be done in this way....