jump to navigation

New game: Toy Story 3! June 9, 2010

Posted by Cesar in working me.
Tags: , , , ,
2 comments

Toy Story 3

I’m proud to say that my latest project here at Other Ocean, Toy Story 3 for the Leapster Explorer,was recently announced!

The Leapster Explorer is a gaming platform from Leap Frog and has a heavy focus on kids and educational content. But don’t be fooled by the colorful look of the device. The Leapster Explorer has a very solid performance and the touch screen only adds to the fun. It was announced yesterday (I guess most kids don’t care about the iPhone 4) and is being very well received.

Toy Story 3 was a joy to develop. It follows a style similar to Mario Party, with board games and plenty of mini-games. Working with the game logic was fun and the development cycle had several interesting challenges. But the best part was dealing with the Toy Story 3 characters. Our team did so well with the animations! I had a lot of fun just watching things happen on the screen.

Congratulations to everyone involved, that was a job very well done.

See you space cowboys…

Advertisements

AI navigation in Left 4 Dead: Part I February 25, 2010

Posted by Cesar in gaming me, working me.
Tags: , , , , , ,
1 comment so far

The other day my good friend (and great game designer) Bruno Palermo pointed me to this presentation that Mike Booth used last year at the Artificial Intelligence and Interactive Digital Entertainment Conference. I found it extremely interesting and useful. I didn’t know Valve made publication material available through their website!

I didn’t have the pleasure to watch it, but by the slides you can tell his presentation goes through a lot of cool stuff. So what I want to do is focus only in the AI for pathing and movement and try to get closer to an actual implementation of the system. See it as my version of the presentation. Is that possible? I think it is, let’s try (I didn’t think this through when writing, but if you are reading it is because it worked. Don’t worry and continue reading).

The most important thing is to remember that the goal is not the best possible behavior but instead the most realistic one. And an exact, perfect path or movement is not very realistic. So let’s begin.

To move the bots (let’s call them bots, right?), the system works in two phases: path finding and movement. One could think after path finding, moving is easy. Well, it isn’t. The L4D system computes the paths in a navigation mesh and the bots extract a rough direction from the path finding system, not an exact guide on how to get from point A to point B. That means it is up to the movement phase to figure out how to reach the next point in the path (jumping, climbing, crouching, whatever).

So the very first step towards the navigation AI is to generate or edit a navigation mesh for the map. I won’t get into specifics (googling navigation mesh should be a good start), but essentially the algorithm tracks “walkable” areas from the map and then grows rectangles in a way that best fits the areas. The result should be a graph-like structure with a bunch of bounding boxes representing areas where the bots can walk. If a bot can move between boxes, we add a bidirectional connection connecting them.

With the mesh properly generated (never at run-time, eh?), the path finding algorithm goes through the graph with a simple A* algorithm. After running A* in our walkable rectangles graph, we have an ordered list of rectangles in the path. At this point it is obvious things are already imprecise, which means the movement phase has to find the best way to go from one rectangle to the other.

The optimal approach, rejected by Booth because it looks robotic, is to look for the rectangle further away with a clear, direct path to it. Because the pathing system is not the only one acting on the bot at run-time (there’s also flocking, small obstacle avoidance, etc), this alternative also requires a lot of repathing: every time something obstructs the path to the target node, the system would have to compute a new path.

Instead, the navigation system uses what Booth calls Reactive Path Following. The decision is very local and sets as a target the unobstructed node further down the path in the direction the bot is facing. Booth mentions this makes the path fluid which wouldn’t be true unless some steering behavior were in place, so here’s my very high level interpretation of that algorithm:

// Rough example of the path update function.
void Bot::PathUpdate(f32 m_fDeltaTime)
{
	// unless the bot got too far from the path, we don't have to compute it
	// again. In this case, the realism of the algorithm helps performance!
	// Of course we also have to find a path if we don't have one yet.
	if (!HasPath() || (DistanceFromPath() > m_fMaxPathDistance))
	{
		m_lPathNodes = AStar::FindPath(
			m_pWorld->GetNavigationMesh(),
			m_vPosition,
			m_vTarget);
		m_iCurrentNode = 0;
	}

	// looking for the best node to track. Notice that the next node is local,
	// the decision is made every frame.
	Node* pNextNode = m_lPathNodes[m_iCurrentNode];
	for (s32 i = m_iCurrentNode; i < m_lPathNodes.GetSize(); ++i)
	{
		if (IsFacing(m_lPathNodes[i]) && IsClearPath(m_lPathNodes[i]))
		{
			pNextNode = m_lPathNodes[i];
		}
	}

	// assuming some complex heuristic might take place to decide which
	// priority each system gets, we don't update the member variables
	// directly. Instead, make requests informing the current system
	RequestMovement(
		ComputePathTranslation(m_fDeltaTime),
		ComputePathSteering(pNextNode, m_fDeltaTime),
		PATH_FOLLOWING);
}

Ok, that’s it for path finding and basic path following but there’s a lot more to cover. However, I haven’t posted for a really long time and it would take me another week to finish the whole subject. So let’s stop at this point and in the next post I’ll continue to object avoidance and ledge climbing.

See you space cowboys…

Unreal Engine now free November 5, 2009

Posted by Cesar in working me.
Tags: , , , , , , ,
add a comment

epic

This is very interesting news for game programmers.  Epic recently made the Unreal Engine available for free and now joins Unity in the land of free engines.

The UDK has all you need to develop a game powered by Unreal Engine 3: editor, animations framework  and physics powered by NVIDIA’s PhysX. This is very useful not only for programmers willing to develop personal projects but also for professionals who want to get a grasp on the technology.

Careful though, the UDK is only free for non-commercial purposes. Anyway, I know where I am going for my next personal gameplay project.

See you space cowboys…

%d bloggers like this: