Progress in movement algorithm design

The album Bolero Gypsies: new flamenco is playing in my ears and the book iPhone cool projects from apress is spread open on my lap and I am typing a blog update on the iPod touch.

The chapter in the book I am reading is about the subject of networking. This may be getting ahead of myself, but it’s good to know for when the opportunity presents itself, and it will.

Yesterday, I created the movement of one of the principle game assets that will be moving constantly in the game. Let’s call this object a “bird” (it’s not in the game, neither is it in the air but it serves for this explanation).  The movement requires intelligence, not merely a simple movement like a rotation of some degrees on every game loop (eg. coins in Super Mario games or rings in Sonic the Hedgehog games). The game world may be large when the game is finished. The first draft for movement has become the following: a “home path” in the same style of the common footpath worn by animals in their native environments, when they travel the paths frequently. So it is with this movent. A path throughout any part of the game world.

This path is achieved by using a number of data variables.

The most important is the array of “checkpoints”. These are the same as checkpoints in a racetrack. In my first version of the movement system, the checkpoints are created as cubes in the world 3d model file, with special object names and serial number prefixes, such as “homepath001”. The name is searched and all the points are loaded into an array.

After the array, the most important variable is for storing the index serial number for the checkpoint the bird will be moving toward. Optionally, this destination may be interupted an replaced with any arbitrary location and the bird will move toward there instead.

Now, storing the index value of the next checkpoint allows us to determine the direction of movement whenever we want to. So now, this permits us to consider other random travel destinations.  If any arbitrary destination is chosen at anytime, another variable must store the yes/no status indicating if the object is moving toward the next checkpoint or not. So this possibility brings the necessity of another variable to store the actual destination location instead of only referencing the next checkpoint from the next-checkpoint-index. When the next checkpoint is reached, the index of the next checkpoint is updated, and the location for the new next-checkpoint is copied to this destination as the default destination.

This is just the tip of the iceberg.

Assuming movement toward some arbitrary location is part of the object’s life cycle, not only following a path forever, then it stands to reason to store not only the next destination separate to the next checkpoint as we’ve discussed, but also store the current home-path-location of the bird as soon as a new, arbitrary, destination is created. This will give the bird next-destination options to choose between, when it reaches the arbitrary location.  It may chose to return to it’s home path from where it left the path, somewhat tracing it’s path backward. Or, it may choose to continue to the next checkpoint directly.

In the case of the city pigeon bird, a home path might be the path around a large office building, and its checkpoints are lamp posts and parking lots (it may choose to walk in a parking lot).  When it is anywhere flying or walking, it may decide to go look at something away from its path, but it will try to keep its home building in sight, and if it decides to return, it can go onto wherever it wants, in the direction of its home!

Having more options is always a better thing than few options or only one.

Following this, I have implemented bezier curves for a smooth transition from approaching one checkpoint to the start of the next checkpoint’s path.  It doesn’t work well if a bird (or any other creature) is moving in a straight line and then instantly is moving in a separate direction..

Never before have I worked with bezier curve equations, so it’s brand new.  But I got the equation from Wikipedia’s page and plugged it in, and now it works.  This is a complicated issue, and not really part of algorithm design, but of implementation.

That will remain for some other day.

This entry was posted in Technology and tagged , , , , , , . Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *