I'm a software engineer who works on game development part time. I teach game development (on gamedev.stackexchange.com and lynda.com). I'm always working on something, and I'll post updates here. Let me know if there's a game development topic you want to know more about, I probably know the answer, or at least where to get one.

Tuesday, April 24, 2012

Gettin' around (a look at AoG path finding)

At the root of it all, the path finding for Age of Goblins isn’t that unique. The base algorithm is A*. However, it has some pretty nifty additions.

The Path Layer

Like most of Age of Goblins at the moment, all the cool stuff is hidden from view. The path finding layer is no exception. This is an invisible layer that sits on top of the terrain. It holds some pretty useful information:
  • Zone: Zones define connectivity. This makes for a quick check to see if a goblin can reach another part of the world. If two points are not in the same zone it means one can not reach the other (don’t waste your time searching). However, if they are in the same zone, that means we can find a path so start the search for the optimal one.
  • Score: The score is kind of a mixing pot for a lot of information about a location in the world. This score is taken into account when finding an optimal path. The higher the score the more likely it will be used in a path.
    • Reasons a location may have its score increased: it was part of a successful path, it’s close to home, it’s in the shade, it’s near automated defenses, or a goblin found a penny there once.
    • Reasons a location may have its score reduced: it was part of a failed path, it’s out in the sun, a goblin was attacked here, enemies sometimes hangout near by, it’s far from safety or a goblin once lost a penny there.

Pathing Tokens

When paths are generated they are a good deal better than just a list of points to travel to. All the entities in Age of Goblins get around using Pathing Tokens. These tokens all contain a position, a token type and a pointer to the next token. The tokens not only tell the entities where to go they tell them how to get there. For example, the most basic token type is ‘Move’. This simply tells the entity to move towards the position contained in the token. The type of moving is governed by the entity, be it: walk, run, slither, crawl or ooze. More interesting types of tokens are a few like: ‘ClimbUp’, ‘ClimbDown’, ‘Stop’, and more. Climb up and down are obviously very useful for changing the animation, speed of movement and direction of movement. Stop is useful for knowing when the path is ending or when we’re about to get to a cube we need to climb. There are others like ‘TakeFlight’ and ‘Land’ that’ll tell flying creatures/gadgets which part of their paths require them to go airborne and when to land to scuttle along on the ground.

Finally here’s a little debug screen shot. The two vertical lines, red and yellow, represent the next and current (respectively) pathing tokens. The red being a ClimbUp token and the yellow being a Stop token. The red line under the goblin represents his acceleration, and as you can see he’s slowing down to the Stop token. He’ll then stop at the base of the wall, and proceed to climb up to the top. It doesn't look fantastic without animation, but I’m no animator so those come later :)

No comments:

Post a Comment