Sorry your browser is not supported!

Hello all!

Ok, the title of this thread doesn't really help but;
I have a grid system, on which the characters are positioned.

The coordinates and status (if the square has a character on it)
of each square is stored in an array.

I can show the squares the player can move to in a 1,2 or 3 square radius like this:


If you're still following my rubbish explanation then I think you deserve a medal!

Ok, that's all good, but what if a character is standing 1 square right of the player but the player's move radius is 2? The player can move 'through' the other character:

X X X X X X X
X O O O O O X
X O O O O O X
X O O P C O X
X O O O O O X
X O O O O O X
X X X X X X X
Where:
X=grid position
P=Player
C=Other character
O=Square the player can move to

My question is how can I test if a route is ok or not?

*If you've got any questions about my explanation please ask, I need your help!

Thanks,
BC

[Edit: made diagram and code clearer]

Check all the squares the player would pass through. So don't just check the destination square, but any other one it may pass over.

Yeah, that's ok for going straight down the x or z axis, but what about the corners?
For example:

X X X X X X X
X O O O Z Z X
X O O O C Z X
X O O P O O X
X O O O O O X
X O O O O O X
X X X X X X X

Here, Z marks square which are more than 2 away due to the other character being there.
Any help on how to work out these Z squares?

Thanks

I think the answer to this depends on how complex the maps / obstructions get. For the simple example you've given, I would favour the following:

Let's pick the top left "Z" as the destination. To get there the player has to move up and to the right. The trick is to test whether the play can move upward and then to the right one box at a time.

X X X X X X X
X O O O O Z X
X O O O C O X
X O O P O O X
X O O O O O X
X O O O O O X
X X X X X X X

1: Can the player move up? yes.

X X X X X X X
X O O O O Z X
X O O P C O X
X O O O O O X
X O O O O O X
X O O O O O X
X X X X X X X

2: Can the player move to the right? No.
3: Can the player move up? Yes. The player is directly to the right of the target square so we don't need to do any more upward movement.

X X X X X X X
X O O P O Z X
X O O O C O X
X O O 0 O O X
X O O O O O X
X O O O O O X
X X X X X X X

4: Can the player move to the right? Yes.

X X X X X X X
X O O O P Z X
X O O O C O X
X O O 0 O O X
X O O O O O X
X O O O O O X
X X X X X X X

5: Can the player move to the right? Yes.

X X X X X X X
X O O O O P X
X O O O C O X
X O O 0 O O X
X O O O O O X
X O O O O O X
X X X X X X X

6: Target reached.

7: So the movement is, 2 up and 2 to the right.

If we pick the "Z" square to the right of the "C" and use the same method:

X X X X X X X
X O O O O O X
X O O O C Z X
X O O P O O X
X O O O O O X
X O O O O O X
X X X X X X X

1: Can the player move up? Yes. The player is directly to the right of the target square so we don't need to do any more upward movement.

X X X X X X X
X O O O O O X
X O O P C Z X
X O O O O O X
X O O O O O X
X O O O O O X
X X X X X X X

2: Can the player move to the right? No.
3: Start again.

X X X X X X X
X O O O O O X
X O O O C Z X
X O O P O O X
X O O O O O X
X O O O O O X
X X X X X X X


4: Can the player move to the right? Yes.

X X X X X X X
X O O O O O X
X O O O C Z X
X O O O P O X
X O O O O O X
X O O O O O X
X X X X X X X

5: Can the player move up? No.
6: Can the player move to the right? Yes. The player is directly under the target square so we don't need to do any more sideways movement.

X X X X X X X
X O O O O O X
X O O O C Z X
X O O O O P X
X O O O O O X
X O O O O O X
X X X X X X X

7: Can the player move upward? Yes.

X X X X X X X
X O O O O O X
X O O O C P X
X O O O O O X
X O O O O O X
X O O O O O X
X X X X X X X

8: Target reached.

9: So the final movement is: 2 to the right and 1 up.

All these checks would be done before the screen is refreshed so you wouldn't see the moves that didn't enable the player to reach the target square. You could also randomise whether you check vertical or horizontal movement.

I've used a method like this before but found for more complex maps and moving a greater number of squares it was easy for the player (in this case it was an computer controlled entity) to get trapped down a dead end.

The other option is to have a look at A* path finding, there are some examples on the forums (can't remember any of hand) but this might be a bit of an overkill as you're only checking a few squares ahead.

@29 games: Thanks for the input!

I'm planning to do this in an RPG battle system, so the playing area is limited to around 10x10 max. A* path finding would do the trick, but the point is I don't care how to get there, only if it is possible in the character's moves per turn quota (which is fairly easy using a counter with 29 games' method).

The description 29 games gave is good and clear, but frankly I'm not sure how to go about doing this as randomisation sounds a bit inefficient but I'm not sure what an analytical method would be. Any chance of some psudo-code from anyone?

Thanks,

[Edit: That sounds a bit more 'giv me da codzz' than I wanted but it's far to late at the moment ]

I think the easiest all encompassing approach is to treat the game grid like plotting lines on a graph.

You'll get a line from point A to Point B. Check the line at 5 points along it on the X axis, getting Y values. Then take those ugly decimal numbers and use Int() or an integer rounding function to convert those numbers to co-ordinates. Then check the co-ordinates for collision.

Long story short, check the line of sight to the target, and convert numbers to integers, so game grid tiles can be checked for collision.

It might need some tweaking but it's a procedural method that will work in any situation without massive volumes of code.

Mage's suggestion is good, simple too! I'll try it and see how it goes.

Thanks,

move line across the box
click mouse to set new ray position
simple test program to see the working of a 2d and 3d
ray box intersections where right

to make it work in 3d just give all the Z Coordinates some values


copy code below into DBP

#Constant INFINITY 99999999.9

// 3d point / vector
Type tVec
x as float
y as float
z as float
EndType

// 3d line / ray
Type tRay
x as float
y as float
z as float
u as float
v as float
w as float
EndType

// 3d box / cube
Type tBox
x1 as float
y1 as float
z1 as float
x2 as float
y2 as float
z2 as float
co as integer
EndType

// holds the in / out intersection points
Type tInfo
tmin as float
tmax as float
EndType

// global intersection info as cant return 2 params from a func
Global t_data as tInfo

//3d line / ray
cray as tRay

// axis aligned box / cube
aabb as tBox

// define a 2d box / cube
aabb.x1 = 128
aabb.y1 = 64
aabb.z1 = 0

aabb.x2 = aabb.x1 + 164
aabb.y2 = aabb.y1 + 164
aabb.z2 = 0

// starting point for the line / ray
cray.x = 0
cray.y = 0
cray.z = 0

// set up display
sync on
sync rate 0
set display mode 480,480,32

// main
repeat

// get mouse coords
mx = mousex()
my = mousey()

// set new line / ray starting point
if mouseclick()
cray.x = mx
cray.y = my
endif

//
cls 0x0

// show the box / cube visually
DrawBox( aabb.x1 , aabb.y1 , aabb.x2 , aabb.y2 , rgb(255,255,255) )

// show the line / ray visually
line cray.x , cray.y , mx , my

// get new direction of line / ray if mouse was clicked
dx# = mx - cray.x
dy# = my - cray.y

// get inverse length
di# = 1. / sqrt( dx# * dx# + dy# * dy# )

// set and normalize line / ray's direction
cray.u = dx# * di#
cray.v = dy# * di#
cray.w = 0

// check if line / box intersected
if RayBoxIntersect( cray , aabb ) = 1
// enter hit
cx# = cray.x + t_data.tmin * cray.u
cy# = cray.y + t_data.tmin * cray.v
ink rgb(255,255,0),0x0
circle cx#,cy#,8
// exit hit
qx# = cray.x + t_data.tmax * cray.u
qy# = cray.y + t_data.tmax * cray.v
ink rgb(255,255,0),0x0
circle qx#,qy#,8
// now a simple 2d ray march
stp = 10
sx# = (cx# - qx#)/(stp-1)
sy# = (cy# - qy#)/(stp-1)
rx# = qx#
ry# = qy#
for i = 0 to stp -1
ink rgb(55,255,255),0x0
circle rx#,ry#,4
rx# = rx# + sx#
ry# = ry# + sy#
next
//
endif

text 10 , 260 , "done."

sync

until escapekey()

end

Function DrawBox(x1,y1,x2,y2,pc)
ink pc,0x0
line x1,y1,x2,y1
line x2,y1,x2,y2
line x2,y2,x1,y2
line x1,y1,x1,y2
EndFunction

Function RayBoxIntersect( ray as tRay , aabb as tBox )

local t1 as float
local t2 as float
local tp as float
local tu as float
local tv as float
local tw as float

t_data.tmin = -INFINITY
t_data.tmax = INFINITY

tu = 1. / ray.u
tv = 1. / ray.v
tw = 1. / ray.w

if tu = 0
if ray.x < aabb.x1 or ray.x > aabb.x2 then exitfunction -1
else
t1 = ( aabb.x1 - ray.x ) * tu
t2 = ( aabb.x2 - ray.x ) * tu
if t1 > t2
tm = t1
t1 = t2
t2 = tm
endif
if t1 > t_data.tmin then t_data.tmin = t1
if t2 < t_data.tmax then t_data.tmax = t2
if t_data.tmin > t_data.tmax then exitfunction -1
if t_data.tmax < 0 then exitfunction -1
endif

if tv = 0
if ray.y < aabb.y1 or ray.y > aabb.y2 then exitfunction -1
else
t1 = ( aabb.y1 - ray.y ) * tv
t2 = ( aabb.y2 - ray.y ) * tv
if t1 > t2
tm = t1
t1 = t2
t2 = tm
endif
if t1 > t_data.tmin then t_data.tmin = t1
if t2 < t_data.tmax then t_data.tmax = t2
if t_data.tmin > t_data.tmax then exitfunction -1
if t_data.tmax < 0 then exitfunction -1
endif

if tw = 0
if ray.z < aabb.z1 or ray.z > aabb.z2 then exitfunction -1
else
t1 = ( aabb.z1 - ray.z ) * tw
t2 = ( aabb.z2 - ray.z ) * tw
if t1 > t2
tm = t1
t1 = t2
t2 = tm
endif
if t1 > t_data.tmin then t_data.tmin = t1
if t2 < t_data.tmax then t_data.tmax = t2
if t_data.tmin > t_data.tmax then exitfunction -1
if t_data.tmax < 0 then exitfunction -1
endif

EndFunction 1

Use code backets please.