AI Experimentation

Collapse is a game set in a post-apocalyptic world in which a human-created AI faction known as the Mechs have taken over. Therefore, AI must be an essential part of the programming.
After extensive research in path-finding algorithms, I decided upon the ubiquitous A*. Then, after days of trying to implement it, using many different techniques from just simple std::vector<Node*> lists to a much more complex and efficient std::priority_queue<Node> binary heap, I gave up. None of them worked properly, obviously due to faults in my programming, but I simple couldn't figure it out.
So I settled on a different approach: pre-defined movement paths. Obviously, this would significantly dumb-down AI decision-making, but I had to at least get something working. The map worked fine, but, again, after days of tweaking and planning and modifying, I couldn't even get the enemy tank to follow the path. I used a rather strange approach with lots of vector math and collision detection, which probably wasn't necessary. The algorithm (in pseudo-code) looked something like this:

Spawn:

    Target = FindNearestPath

    End

Update:

    If reached Target

        Target = FindNextTile

        If no Target

            Turn 3 degrees

    Else

        Adjust angle and drive.

    End

FindNearestPath:

    Find tile with minimum distance to entity.

    Return tile

FindNextTile:

    For each tile in AI map

        If tile collides with line-of-sight

          and tile not collides with entity

            Return tile

    Return no tile

Basically, that's what would happen every frame. If a target couldn't be found, the enemy would keep turning in a circle until its line-of-sight (a line segment with a length of 64 pixels protruding out from the front-center of the tank) hit a tile, then the tank would move towards it. As with anything, it didn't go exactly as expected. First, my vector-line-rect collision detection was extremely wrong. I spent near 2 days trying to figure it out. I used many techniques, most of them based on vector cross products and whatnot, but ended up going with a much simpler algebraic approach. I just determined the infinite line equation of the two line segments and found their intersection point. Then I checked if the intersection point was in the range of the line segments. If it was, there's a collision! If not, well, no collision, obviously. The source code looks like this, if anyone is interested: 

	/**
	* Checks for intersection with another line segment. Touching at
	* endpoints qualifies as intersections.
	*
	* @param math::CRay2 The other line
	*
	* @return TRUE if they intersect, FALSE otherwise.
	* @see http://gamedev.stackexchange.com/questions/26004/how-to-detect-2d-line-on-line-collision
	**/
	bool CRay2::CheckCollision(const CRay2& Other, math::CVector2* p_Intersection) const
	{
	/**
	* Solve for the intersection point.
	*
	* Derivation:
	* First line: y - y1 = m1(x - x1)
	* Second line: y - y2 = m2(x - x2)
	* Equal to each other: m1x - m1x1 + y1 = m2x - m2x2 + y2
	* Solve for 'x': m1x - m2x = -m2x2 + y2 + m1x1 + y1
	* x(m1 - m2) = -m2x2 + y2 + m1x1 + y1
	* x = (-m2x2 + y2 + m1x1 + y1) / (m1 - m2)
	* Solve for 'y': y = m1(x) - m1x1 + y1
	* Thus (x, y) becomes the intersection point.
	*
	* Then we must see if (x, y) is in the range of line segments given.
	**/
	math::CVector2 Intersect;
	float m1, m2;
	m1 = this->GetSlope();
	m2 = Other.GetSlope();
	// Test for infinite slopes or parallel lines.
	if(this->Start.x == this->End.x)
	Intersect.x = this->Start.x;
	else if(Other.Start.x == Other.End.x)
	Intersect.x = Other.Start.x;
	else if(m1 == m2)
	return false;
	else
	Intersect.x = (-m2 * Other.Start.x + Other.Start.y + m1 * this->Start.x - this->Start.y) / (m1 - m2);
	Intersect.y = m1 * Intersect.x - m1 * this->Start.x + this->Start.y;
	if(this->OnRay(Intersect) && Other.OnRay(Intersect))
	{
	if(p_Intersection != NULL)
	*p_Intersection = Intersect;
	return true;
	}
	else
	return false;
	}

view raw RayCollision.cpp hosted with ❤ by GitHub

Well, after jumping through all of these hurdles, I decided that it's time to take a look at A* and dynamic path-building/finding. Hopefully with this optimized collision detection approach that doesn't involve dozens of tiny rectangles representing a line, A* combined with line-of-sight target location will be much more effective.