On waypoint graphs

As promised, a first post on path finding solutions for games. The first structure I’m going to treat are so called waypoint graphs, and are still commonly used in games regardless of their downsides, mainly because of their simplicity.

A waypoint graph is actually a very simple concept; positions in the free space (so, the area that a character is supposed to be walking on) are sampled either by hand or by algorithm, and n‑nearest neighbor points are connected to the newly sampled point by an edge if no obstacles are detected between the two points. It is one of the most classical solutions used in games, and is still being used by games today. Short paths are found by applying A* on the graph. Start and goal configurations would be added to the graph as temporal waypoints and characters would move from waypoint to waypoint until the goal is reached.The problem with this is method of course is that it doesn’t give any idea on the boundaries of the free space, so the coverage cannot be optimal by definition and is dependent on how many waypoints are used. In other words, characters are stuck to using waypoint routes, and deviating from the path isn’t really possible unless you perform a collision test on the intermediate path to check if it doesn’t hit any obstacles. On of the games that recently came out still uses this technique; Alien Swarm by Valve. In Alien Swarm there are many waypoints, and they are all connected with a lot of neighboring points. Collision detection is used to check if a path is actually valid and disabled if not (see screenshots). The main reason this is done is because the environment can be dynamic. For the paths in a limited area where the environment is dynamic and changing, new paths are added if they are free from collisions with the changed environment.

Waypoint graphs can also be extended to include a radius. These kind of graphs are sometimes referred to as circle-based waypoint graphs. The idea is that characters may only traverse from waypoint to waypoint if their circles are intersecting. The improvement over a simple waypoint graph is that a circle-based waypoint graph approximates the free space. The problem is that when waypoints are placed in arbitrary locations, the approximation of the free space may still be fairly inaccurate, which means that characters still can’t reach locations that are visibly reachable. Also, the denser the environment is, the more waypoints you will need generally because the circles of the waypoints are smaller. By placing the waypoints along the medial axis of the environment (the axis on which the distance to two different obstacles is equal) you can insure connectivity.

Next time more on waypoint graphs πŸ˜‰

By the way, Alien Swarm is freely available on Steam.

Some nice new videos on Path Planning

So, recently there have been a couple of new videos that illustrate ‘new’ techniques in path planning and especially crowd simulation for games. The first is on so called flow fields in supreme commander. Although it is a really nice new way of doing things, especially in the example where large units move to a group of smaller ones the behavior to my opinion is still unnatural as small units literally get pushed out of the way:

And the second is on path planning in the upcoming Starcraft 2; I don’t really know much about the techniques used here, but it looks as if they combine local force methods with A*. It looks cool but again the behavior of the zerglings sometimes is a bit unnatural still, some odd patterns can be seen when the units are packed together:

'New' Blogpost :p

In light of my thesis project, I said to try to blog more and focus a bit more on the subject of my research, which is about path planning for characters in virtual worlds, specifically related to constructing paths in complex 3D environments (environments which have tunnels, bridges and such). I still intend to do so πŸ˜‰. I’m not yet sure on where to begin, but I will make it thorough and worth reading for one πŸ™‚ I’ll cover A* of course, one of the most famous of path finding algorithms, but I will also move on to other things, like navigation graphs and navigation meshes, and also some lesser known methods such as the corridor map method which is being developed at Utrecht University (and where I am working on to do path planning in 3D environments). I might also consider several methods to simulate crowds as well, since games tend to get larger and larger and therefore whole cities are being populated with characters which move through the city (for example in the Assassins Creed series and the Grand Theft Auto series). To be continued… πŸ˜‰

Whats going on !?

So it’s been quite some time since I last blogged, a lot of stuff happened since, so it’s about time I’d blog again. The experimentation project in the end didn’t turn out to go very well as for the game, but a lot of lessons learnt nevertheless. The only thing left to do is write a document on how best to incorporate Ogre3D within a game (engine), as I changed my topic to reflect my tasks within the project more (didn’t do much special camera stuff as there was no time). The game I was supposed to make for DBP didn’t go through as my experimentation project took all of my time troughout the summer, which is a bit unfortunate.
Fortunately I finished some courses as well; I did a course on Path Planning and Crowd Simulation which was really cool, and I retried for Motion and Manipulation, which is essentially a robotics course mostly related to planning paths for robots that have a certain degree of freedom, forward kinematics for robot arms (and thus also skeletons in games), high level collision detection and the grasping of objects and such. The course has a lot of things in common with other courses like path planning, but also computational geometry and virtual worlds which itself is mostly about physics and network related aspects of virtual environments. Having finished that course which was actually my last one, I am now preparing to begin my Thesis project πŸ™‚

Blues for the red sun

I realised I haven’t posted in a while so here is a status update πŸ™‚

I’ve installed a twitter add-in on my blog to keep you up-to-date on small blog related things, surfing the hype. I think its a rediculous concept in-all especially when it is used by large commercial news website and others, because I really don’t care if they just placed a new news item on the news site. I discover new news when i actually visit, so adding twitter is just out of context there. I like the micro-blogging aspect though, but people abuse it to enlighten us followers that they are taking a crap. I try not to abuse it, and make it relevant to this blog so that it keeps interesting. So much for that πŸ˜‰

The experimention project is going along. I’ve been setting up the main game structure, and I’m working on the whole camera system. The camera system is something I’ll be going into further in a later post, because it is also my main research topic. We are roughly four weeks in production, and we’ve got a flock of birds flying around and interaction between the flock and the thing we call sources, attracting the flock when clicked upon. We’re currently working towards an alpha version which includes the city as well, to get a nice impression of what it is going to be like.

DreamBuildPlay has started and me and a couple of guys are making a game for it. We have some really cool ideas to elaborate on. We are aiming at combining aspects of geometry wars and more classical vertical-scrolling shooters like raptor or tyrian. Simple, slick graphics and chaos is what we’re aiming for, and 3D ofcourse. More later on that, as it is XNA I will probably do some articles on it.

This weekend is LudumDare weekend and I’m attending. Voting for a subject is this week, and until it gets underway on friday night. Then its 48h of game making mayhem. Some guys at ludumdare irc are doing daily sketchblogs to improve on their drawing skills. It sounds interesting enough so I’ve decided to give that a try as well; I don’t know when though, but probably soon enough ;).

Thats it for now, until later πŸ˜‰