next »

[Qqwy]

Hello there. For my game, I want to create enemies that will only activate/move towards the player as soon as they can actually see him.
I am guessing to detect if the player can be seen, I create a straight line between the enemy position and the player position, and check if that line overlaps with any parts of the level. If this is not the case, the player can be seen.

My level is stored as square tiles in a QuadTree. How do I check if the line overlaps any tiles?

[z84c00]

Bunch of ways of doing this.

Geometric way: Since you're using a quad-tree you can eliminate a whole bunch of tiles, the remaining ones, based on your view direction and fov, can be checked using line / box intersection. Early out would speed this up.

Using rendering: use the zbuffer / stencil buffer to figure out if you've got an writes.

Computational: Use bresenham line algorithm and step through all the tiles along the line. First hit earlies out. Depends on how many tiles you have and how far you can see.

Precompute! Depends on the level size and whether or not you have a lot of other dynamic objects (actually, all of the above need to take that into account ). For each tile in the grid, create a list of tiles you can see from that position :-)

-z8

[Gregg Williams]

z8 really summed it up, though I'd recommend just starting with the likely simplest version. Do a quick distance check from the enemy to the player, and only if within possible activation radius than do a quick bresenham line across tiles to check for blockages.

You can also easy add a nice realistic reaction time/delay to this process as well if desired, by having the AI only do a check every X frames.

[Columbo]

Bresenham isn't quite ideal for collision detection because it can miss some cells that the ray actually travels through, potentially letting the AI see through corners of walls slightly.

I've used an algorithm from Crister Ericson's Real Time Collision Detection to walk the grid, but I can't find that online, so here's a link to what I think is the same solution http://stackoverflow.com/questions/13542925/line-rasterization-4-connected-bresenham

[BorisTheBrave]

I wrote this once. You can adapt the standard grid walking code linked above fairly easily to work with quad trees. Each subdivision is a "grid" of four tiles, walk them with the algorithm. Each tile you pass through that is a sub tree, recurse.

Edit: here's some code. It's C++, and maybe could be more readable, but it's tested. b2TaggedQuadCell is the address of a quad cell, while b2QuadTreeOutput stores if the give cell is solid, empty, or has children.

Code:

// Sort cells so that they are ordered by what a vector of direction v would hit them in.
// The cells should all have the same depth
void BubbleSortCells(b2TaggedQuadCell* cells, int32 cellCount, const b2Vec2& r, const b2Vec2& abs_r)
{
for(int32 i=1;i<cellCount;i++)
{
if(i<1) continue;
b2TaggedQuadCell& cell1 = cells[i];
b2TaggedQuadCell& cell2 = cells[i-1];
bool lessThan;
if(abs_r.x > abs_r.y)
{
if(cell1.xOffset != cell2.xOffset)
lessThan = (cell1.xOffset < cell2.xOffset) ^ (r.x > 0.0f);
else if(cell1.yOffset != cell2.yOffset)
lessThan = (cell1.yOffset < cell2.yOffset) ^ (r.y > 0.0f);
else
lessThan = false;
}else{
if(cell1.yOffset != cell2.yOffset)
lessThan = (cell1.yOffset < cell2.yOffset) ^ (r.y > 0.0f);
else if(cell1.xOffset != cell2.xOffset)
lessThan = (cell1.xOffset < cell2.xOffset) ^ (r.x > 0.0f);
else
lessThan = false;
}
if(lessThan)
{
b2Swap(cell1, cell2);
i -= 2;
}
}
}

bool b2QuadTreeShape::RayCast(b2RayCastOutput* output, const b2RayCastInput& input,
const b2Transform& transform, int32 childIndex) const
{

b2Vec2 p1 = b2MulT(transform, input.p1);
b2Vec2 p2 = b2MulT(transform, input.p2);
b2Vec2 r = p2 - p1;
b2Assert(r.LengthSquared() > 0.0f);
float32 len = r.Normalize();
b2Vec2 abs_r = b2Abs(r);

b2TaggedQuadCell cells[4];
b2AABB aabb;
GetAABB(&aabb);
int32 cellCount = b2TaggedQuadCell::GetCoverage(aabb, cells);

// We arrange the stack so that cells are in reverse order of traversal by the ray.
// This means we can exit immediately when we find a hit, as all cells still in the
// stack get hit later.
b2GrowableStack<b2TaggedQuadCell, 256> cellStack;

BubbleSortCells(cells, cellCount, r, abs_r);
for(int32 i=0;i<cellCount;i++)
cellStack.Push(cells[i]);


while(cellStack.GetCount() > 0)
{
b2TaggedQuadCell cell = cellStack.Pop();

b2QuadTreeOutput treeOutput;
EvaluateTree(cell, treeOutput);
if(treeOutput.type == e_empty)
continue;

b2Vec2 c = cell.GetMidpoint();
float32 halfSize = cell.GetSize() / 2.0f;
b2Vec2 h = b2Vec2(halfSize, halfSize);

b2Vec2 localP = p1 - c;
b2Vec2 abs_localP = b2Abs(localP);

// Min & max are give the interval by distance along the ray that
// Is inside the polygon being considered
// This is similar to b2Polygon's raycast, but optimized for an AABB.
float32 min = 0.0f;
float32 max = len * input.maxFraction;

enum Side {
e_startsInside,
e_lowerX,
e_upperX,
e_lowerY,
e_upperY,
} side = e_startsInside;

if(abs_r.x > b2_epsilon)
{
float32 minX = -localP.x / r.x - halfSize / abs_r.x;
if(min < minX)
{
min = minX;
side = r.x > 0 ? e_lowerX : e_upperX;
}
min = b2Max(min, minX);
float32 maxX = -localP.x / r.x + halfSize / abs_r.x;
max = b2Min(max, maxX);
}else{
if(abs_localP.x > halfSize)
continue;
}
if(abs_r.y > b2_epsilon)
{
float32 minY = -localP.y / r.y - halfSize / abs_r.y;
if(min < minY)
{
min = minY;
side = r.y > 0 ? e_lowerY : e_upperY;
}
float32 maxY = -localP.y / r.y + halfSize / abs_r.y;
max = b2Min(max, maxY);
}else{
if(abs_localP.y > halfSize)
continue;
}


if(min < max)
{
// Success
if(treeOutput.type == e_solid)
{
switch(side)
{
case e_lowerX: output->normal.Set(-1.0f, 0.0f); break;
case e_lowerY: output->normal.Set(0.0f, -1.0f); break;
case e_upperX: output->normal.Set(1.0f, 0.0f); break;
case e_upperY: output->normal.Set(0.0f, 1.0f); break;
case e_startsInside: output->normal.SetZero(); break;
}
output->fraction = min/len;
return true;
}else{
// Recurse
cellCount = GetChildren(cell, cells);
BubbleSortCells(cells, cellCount, r, abs_r);
for(int32 i=0;i<cellCount;i++)
cellStack.Push(cells[i]);
}
}
}
return false;
}