Contents

Introduction
Character Image
Files
Checking for
Movement
Collision Detection
Animation
NPCs and Random
Movement
Ordering Characters

Printable version
Discuss this article
in the forums

The Series

Beginning Windows
Programming
Using Resources
in Win32 Programs
Tracking Your
Window/Using GDI
Introduction
to DirectX
Palettes and Pixels
in DirectDraw
Bitmapped Graphics
in DirectDraw
Developing the
Game Structure
Basic Tile Engines
Adding Characters
Tips and Tricks

Ordering Characters

As soon as we introduce a second character into the game, we create a new problem for ourselves: the characters must be drawn in the correct order. When two characters who are two tiles tall come within one tile of each other, the one with the lesser y-value had better be drawn first, or the results will look a little strange!

Right Wrong

Right

Wrong

See what I mean? Ordering is the difference between having your characters appearing as they would naturally, or having an old NPC standing on the shoulders of a headless main character. :) What we need to do is make sure that our NPCs are always sorted in order of increasing y-value, so that they get drawn properly. Also, we need to be watching for when the main character should be drawn, because he's part of the order too.

The first thought that comes to mind is a sorting function -- but do you really want to run a full sort every time an NPC moves? If you've got a hundred NPCs, that's going to be a large sort running way too often. What we do instead is to sort the NPCs once, right when they're initialized. Then, anytime an NPC's yTile member changes, we move that element only. Since yTile only changes by 1 at a time, we won't need to run a sort on the whole NPC array. We'll just find the NPC with the next smallest (or next largest, as the case may be) yTile, and swap those two. Much faster. This is also why we created the NPCs as pointers instead of structures. Swapping pointers is faster than swapping the contents of an entire structure.

For that initial sort that runs right when the NPCs are initialized, you can use whatever you like. If the number of NPCs is going to be small, then something like a bubble sort or insertion sort will serve your purposes just fine. If your vision is slightly larger and involves lots of characters all going at once, then you may want to use something a little more high-powered, like QuickSort. The code to keep the array sorted is no problem. We need two cases: one in which the NPC has moved up, and one for if he's moved down. All we do is find the nearest NPC whose y-value is lesser or greater, respectively, then swap the current NPC to be next to that position. Here it is in action for when NPC number nIndex moves upwards:

int nPointer = nIndex;
LPNPC lpnpcTemp;

// first check to see if this is equal to the highest NPC
if (lpnpc[nIndex]->move.yTile > lpnpc[0]->move.yTile)
{
  // nIndex is not highest, so a reordering is required.
  // step up the array until we find the next highest NPC
  while (lpnpc[nPointer - 1]->move.yTile == lpnpc[nIndex]->move.yTile)
    nPointer--;

  // now swap NPCs at nIndex and nPointer
  lpnpcTemp = lpnpc[nPointer];
  lpnpc[nPointer] = lpnpc[nIndex];
  lpnpc[nIndex] = lpnpcTemp;
}
else
{
  // swap with highest NPC
  lpnpcTemp = lpnpc[0];
  lpnpc[0] = lpnpc[nIndex];
  lpnpc[nIndex] = lpnpcTemp;
}

The code for moving down is analogous so I won't bother showing it here. Note that this code might cause some ugly errors if you run it when the NPC array is not sorted, so be careful to implement it correctly!

Well we're just about done here! Our NPCs now move randomly, and the array of NPCs will always be ordered correctly, with minimal work required to keep it that way. The only thing left to do is to render the characters onto the map. Here's how it's done. Immediately after the map itself has been drawn, start searching through the NPC array for the NPC with the smallest y-value who is in the viewable vertical range. This can be done simply by checking the NPC's location against the camera's y-coordinate. From that point, start going through the NPC array one at a time, drawing each character if he is within the viewable horizontal range. Remember that the player must also be drawn at the correct time, so watch the NPC y-values and how they compare to the player character's y-value. The source code uses some variables that are found in the function for rendering maps, so I'll just let you look at the sample source file for this one. Look at how it's set up in RenderMap(), and how it's executed in RenderCharacters().

Closing

This demo of ours is starting to look more and more like a working game, isn't it? Go grab the source code for this article and play with it a little bit. See what you can write on your own without having to look at the source. And then see what you can add to it! Give your NPCs a little bit more freedom by letting them vary from each other a bit more. By adding some data members to the NPC structure, you can make different NPCs walk at different speeds, and more or less often than others. You can allow NPCs to move more than one tile at a time. If you're feeling really ambitious, try giving them some paths to follow. If you visit the GameDev Game Design forum at all, you've probably heard the phrase "NPCs are people too." So don't subject your characters to a lifetime of wandering randomly if you can come up with some better ideas. :)

Well I'm sad to say it, but Game Programming Genesis is just about at an end. I had planned on extending the series to 12 articles and adding a couple more topics, but there are a few reasons for stopping at Part X. For one, my life has gotten a lot crazier in the last week or two, so I've gotten very pressed for time, and these articles take a lot of time to come up with, especially with the demos getting larger all the time. I really wanted to get to scripting, but I realized that it's such a huge topic, I'd have to devote an entire series to it. There's no way I could cover everything I want to say about it in one article. So a new series dedicated to building up this scripting engine I'm always talking about is a real possibility for the not-too-distant future if I get the time to do it.

Next time, in the series' final entry, I'll show you all kinds of assorted tips and tricks for you to implement as you start building our demo into a full game. It'll be a little bit of information on a lot of topics, like generating log files of your programs at runtime, protecting your game data from being changed by end users, and whatever else I come up with in the next few weeks. As always, feel free to E-mail me at ironblayde@aeon-software.com, or find me on ICQ at #53210499, with any questions you have, and I'll see you next time!