The island - An RTS game

[ITomi]

I was just thinking about it, and, I am confused... why exactly do you need 'collision detection'?

The collision detection needs to me to get the distance of the closes edges between two objects. E.g. when I'd like put down a piece of the road close to another piece (not too close but not too far).
It's still rather imprecise at the player.

[Tourist Trap]

I was just thinking about it, and, I am confused... why exactly do you need 'collision detection'?

The collision detection needs to me to get the distance of the closes edges between two objects. E.g. when I'd like put down a piece of the road close to another piece (not too close but not too far).
It's still rather imprecise at the player.

I've made somthing to get the result of overlapping rectangles few months ago. It is quite big due to the project context of then, but maybe it is what you want to do: http://www.freebasic.net/forum/viewtopi ... 47#p214747.

[leopardpm]

The collision detection needs to me to get the distance of the closes edges between two objects. E.g. when I'd like put down a piece of the road close to another piece (not too close but not too far).
It's still rather imprecise at the player.

ah ha! ok... I am assuming then that each 'piece' of road is contained within 1 of the map tiles, right? And the 2 rectangles you are trying to compute the distance between are actually 2 map tiles, right?

so, when placing a piece of road (or any other type of tile that connects with others), then just check the neighboring 4 or 8 map cells to see if there is a tile type you might connect with... you don't care about the 'distance', you actually ONLY care if there is something next to your tile placement, you don't care if there is a road tile across the map, right? You don't need (or want) a distance function for this. BUT, I assume that I might not have all the information regarding what you are doing so you will have to determine if what I am saying is correct in your particular case...

[ITomi]

I try detecting distances between two objects as follows (in this case between the worker (32*32) and a building (width*height)):

Code: Select all

if abs(herex-building(i).xplace)<=33 or abs(herex-(building(i).xplace+building(i).width))<=33 or abs(herey-building(i).yplace)<=33 or abs(herey-(building(i).yplace+building(i).height))<=33 then
      return 1
end if

But it's imprecise; the workers sometimes does his works from the distance... :-/

[ITomi]

I've made somthing to get the result of overlapping rectangles few months ago. It is quite big due to the project context of then, but maybe it is what you want to do: http://www.freebasic.net/forum/viewtopi ... 47#p214747.

I've tried your code just now, but FB threws up the following error messages:

Compiler output:
E:\progsetup\FreeBASIC-0_23_0-win32\sajatprogik\atlapolas.bas(760) error 14: Expected identifier, found 'boolean' in 'dim as boolean hasToExit => FALSE'
E:\progsetup\FreeBASIC-0_23_0-win32\sajatprogik\atlapolas.bas(782) error 41: Variable not declared, hasToExit in 'hasToExit = TRUE'
E:\progsetup\FreeBASIC-0_23_0-win32\sajatprogik\atlapolas.bas(788) error 41: Variable not declared, FALSE in 'hasToExit = FALSE'
E:\progsetup\FreeBASIC-0_23_0-win32\sajatprogik\atlapolas.bas(1321) error 14: Expected identifier, found 'boolean' in 'as boolean _mouseOver'
E:\progsetup\FreeBASIC-0_23_0-win32\sajatprogik\atlapolas.bas(1328) error 14: Expected identifier, found 'boolean' in 'as boolean _clickEnabled'
E:\progsetup\FreeBASIC-0_23_0-win32\sajatprogik\atlapolas.bas(1341) error 14: Expected identifier, found 'boolean' in 'as boolean _markedAsTemporaryNonDraggable'
E:\progsetup\FreeBASIC-0_23_0-win32\sajatprogik\atlapolas.bas(1388) error 18: Element not defined, _clickEnabled in '._clickEnabled => TRUE'
E:\progsetup\FreeBASIC-0_23_0-win32\sajatprogik\atlapolas.bas(1389) error 18: Element not defined, _dragEnabled in '._dragEnabled => TRUE'
E:\progsetup\FreeBASIC-0_23_0-win32\sajatprogik\atlapolas.bas(1390) error 18: Element not defined, _mouseOver in '._mouseOver => FALSE'
E:\progsetup\FreeBASIC-0_23_0-win32\sajatprogik\atlapolas.bas(1391) error 18: Element not defined, _mouseClick in '._mouseClick => FALSE'
E:\progsetup\FreeBASIC-0_23_0-win32\sajatprogik\atlapolas.bas(1391) error 132: Too many errors, exiting

Computing of overlapping means so massive codes like your?

[badidea]

Boolean was recently introduced in freeBASIC. Download the latest compiler or define 'Boolean', 'true' and 'false' yourself.

[Tourist Trap]

I've tried your code just now, but FB threws up the following error messages

Itomi, you use Freebasic 0.23? Why not upgrading for version 1.04 and above? Otherwise you cant run some codes with recent syntax addition like here.

Computing of overlapping means so massive codes like your?

I don't think, it probably can be done with a math algorithm.

[leopardpm]

I try detecting distances between two objects as follows (in this case between the worker (32*32) and a building (width*height)):

Code: Select all

if abs(herex-building(i).xplace)<=33 or abs(herex-(building(i).xplace+building(i).width))<=33 or abs(herey-building(i).yplace)<=33 or abs(herey-(building(i).yplace+building(i).height))<=33 then
      return 1
end if

But it's imprecise; the workers sometimes does his works from the distance... :-/

ok, now this I can wrap my mind around perhaps... brb in a bit, got chores....

[leopardpm]

are you ready? Here we go... first, lets deal in center points: center of worker and center of building rectangle

what we want to do is find the intersection between the line that these two points make, and the lines which define the rectangle (actually, the lines that define the rectangle of the 'worker zone'

I googled "line intersection" and found this page: http://www-cs.ccny.cuny.edu/~wolberg/ca ... lines.html

which gave me the formulas in simple enough terms...

here is some example code, highly commented and bloated - can be reduced down to just a few easy lines...

Code: Select all

' intersection of two lines
'
' line1 (100,100) - (300,200)
' line2 (100,200) - (300, 50)
'
'

dim shared as integer x, y

' Determine intersection of two lines:
sub LineIntersection(byval x1 as integer ,_
                     byval y1 as integer ,_
                     byval x2 as integer ,_
                     byval y2 as integer ,_
                     byval x3 as integer ,_
                     byval y3 as integer ,_
                     byval x4 as integer ,_
                     byval y4 as integer )
dim as single ua, ub
    x = 0 : y = 0
    ua = ( (x4-x3)*(y1-y3) - (y4-y3)*(x1-x3) ) / ( (y4-y3)*(x2-x1) - (x4-x3)*(y2-y1) )
    ub = ( (x2-x1)*(y1-y3) - (y2-y1)*(x1-x3) ) / ( (y4-y3)*(x2-x1) - (x4-x3)*(y2-y1) )
    if ua>0 and ua<1 and ub>0 and ub<1 then ' this checks to make sure the line segments intersects
        y = y1 + ua * (y2 - y1) 
        x = x1 + ua * (x2 - x1)
    end if
end sub

screenres 800,600,32
cls
locate 2,5: print "Just showing the intersection betweemn two lines - hit a key"
'   draw the lines...
line (100,100)-(300,200), rgb(255,0,0)

line (100,200)-(300,50), rgb(255,0,0)

' find intersection...
x = 0 : y = 0
LineIntersection(100,100,300,200,100,200,300,50)

' show the intersection point
circle (x,y),10,rgb(0,255,0)
pset (x,y), rgb(255,255,255)

sleep

' so now that we can do that... lets do it with a rectangle!

type rect   ' defined by upper left corner and lower right corner)
    dim as integer x1
    dim as integer y1
    dim as integer x2
    dim as integer y2
    dim as integer cx
    dim as integer cy
end type

dim worker as rect
dim building as rect
dim wdist as rect   ' this is the rectangle that defines the working distance

dim as integer workdist, IntersectionX, IntersectionY

cls
' worker is a rect 32 x 32
worker.cx = 100 : worker.cy = 100
'don't care about worker rectangle....
worker.x1 = worker.cx - 16 : worker.y1 = worker.cy - 16
worker.x2 = worker.cx + 15 : worker.y2 = worker.cy + 15 ' 16 + 15 + 1(center) = 32 pixels

'draw worker...
line (worker.x1, worker.y1) - (worker.x2, worker.y2), rgb(0,0,255),bf ' blue box

' building is a rect 201 x 121 PLUS a certain distance from the building you want the worker to go to...
' so increase the rectangle by this distance (this is the distance from the building rectangle TO the worker CENTER!
workdist = 16 + 10 ' 16 is to adj from worker center, 10 is the actual distance
building.cx = 300 : building.cy = 200
building.x1 = building.cx - 100 : building.y1 = building.cy - 60
building.x2 = building.cx + 100 : building.y2 = building.cy + 60 ' 60 + 60 + 1(center) = 121 pixels(y)

'draw building...
line (building.x1, building.y1) - (building.x2, building.y2), rgb(255,0,0),bf ' red rectangle

'draw work distance from building....
wdist.x1 = building.x1 - workdist : wdist.y1 = building.y1 - workdist
wdist.x2 = building.x2 + workdist : wdist.y2 = building.y2 + workdist

line (wdist.x1, wdist.y1) - (wdist.x2, wdist.y2), rgb(128,0,0),b ' dim red rectangle, not filled

'draw line between worker and building....
line (worker.cx, worker.cy) - (building.cx, building.cy), rgb(0,64,0) ' dim green line

' now, here is the trick...:
' do a line intersection with all 4 sides of rectangle
'
LineIntersection(worker.cx, worker.cy,   building.cx,building.cy,_ ' line from worker to building
                 wdist.x1, wdist.y1,_       ' top-left corner
                 wdist.x1, wdist.y2)        ' bot-left corner
if x > 0 then IntersectionX = x
if y > 0 then IntersectionY = y

LineIntersection(worker.cx, worker.cy,   building.cx,building.cy,_ ' line from worker to building
                 wdist.x1, wdist.y1,_       ' top-left corner
                 wdist.x2, wdist.y1)        ' top-right corner
if x > 0 then IntersectionX = x
if y > 0 then IntersectionY = y

LineIntersection(worker.cx, worker.cy,   building.cx,building.cy,_ ' line from worker to building
                 wdist.x1, wdist.y2,_       ' bot-left corner
                 wdist.x2, wdist.y2)        ' bot-right corner
if x > 0 then IntersectionX = x
if y > 0 then IntersectionY = y

LineIntersection(worker.cx, worker.cy,   building.cx,building.cy,_ ' line from worker to building
                 wdist.x2, wdist.y1,_       ' top-right corner
                 wdist.x2, wdist.y2)        ' bot-right corner
if x > 0 then IntersectionX = x
if y > 0 then IntersectionY = y

' show the intersection point
locate 2,5 : print "The intersection point is at (";IntersectionX;",";IntersectionY;"), the worker should move to this point!
circle (Intersectionx,Intersectiony),10,rgb(0,255,0)
pset (Intersectionx,Intersectiony), rgb(255,255,255)
sleep
end

thanks for the fun exercise!!! Hopefully this solves your issue

[ITomi]

Yeah, this is it! Big thanks, leopardm! I like visual examples.
I will build it into my program, but now I'm enough busy.
Otherwise I tried to search on the web with regard to this, but I didn't think to "line intersection" keywords and mainly I browse hungarian sites.
Once more, thanks for you and Tourist Trap for your help!

[leopardpm]

glad to be a help to you - lord knows the folks on these forums have helped me out a lot! I look forward to seeing your progress on your game, and feel free to ask any questions you might have in the future

Michael

[ITomi]

I really suggest A*, it is pretty simple once you understand it.

Yes, but whether which method is suitable better for an RTS game? The A* algorythm is lead correctly from a place to another, but I have to check the collisions during this time, too. Then it is the same as my method: the check collisions before pieces of moving, in every step.
What is your opinion about it?

[leopardpm]

how many units will be moving at same time? Will there be multiple units moving to same destination? Will the destinations be static (like forest to chop trees, mountains to mine, etc) or dynamic like any point on the map?

[ITomi]

As I plan, many units will be moving, e.g. workers and warriors. Their destination can be same, which would be a tree for a worker or a moving enemy for the warriors.
The buildings do more complicated the things, because what happening if a building build up on the way, while the unit moves on it with help of A*?

[leopardpm]

As I plan, many units will be moving, e.g. workers and warriors. Their destination can be same, which would be a tree for a worker or a moving enemy for the warriors.
The buildings do more complicated the things, because what happening if a building build up on the way, while the unit moves on it with help of A*?

ok, for moving a group to one destination, you can just make a 'heatmap' (basically Dijkstra’s Algorithm) and it would generate a map for ALL units to follow - to avoid dynamic moving obstacles (each other, etc), they could just 'wait' if a space is temporarily occupied until it is free. If a permanent obstacle appears (wasn't there when the HeatMap was generated) then redoing the heatmap would path around it. One issue would be that all the units would obviously not 'fit' into the one space clicked on for the destination and ideally you would want the units to then spread out and 'surround' the object (in the case of workers sent to build a building) or find another similar object nearby for their use (in the case of a woodchopper picking another tree nearby). These cases could be handled by, again, recreating the heatmap with all the spaces or objects already 'in use' not included... this would be a little trickier, but easy enough. Probably the 'best' way is deal with these cases would be not to use a heatmap at all, and from the start:
(1) get total number of selected units
(2) for each unit, pick a destination space closest to the actual destination 'point'
(3) mark that space as 'not available' for a destination for the next selected unit
(4) A* path each unit to its respective destination (<---- repeat for all units)