I'm developing my first game, Age of Goblins. I develop this part time, and work at a "real" (read: paying) job full time. Age of Goblins is a three dimensional goblin empire building game. Inspired by Dwarf Fortress and Minecraft. Age of Goblins gives a player control over a small band of goblins in a cube-based sandbox world. The player can instruct the goblins to add or remove different types of cubes, build various structures, make elaborate traps, and craft a multitude of items.

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 :)

Thursday, April 19, 2012

A fairly rushed video, just showing a few of the additions to Age of Goblins recently. Now, back to coding!