How to have creatures keeping track of each other in a role playing game

Question

I'm programming a role playing game for fun and to learn. I am planning on having an overall game world and in that game world I plan on having "zones" that players and monsters can move around on. Let's just say the "zones" are 20x20 grids and each "tile" on this grid is 64 pixels wide. A player or monster can occupy one 1x1 tile and move about in steps of 1 tile per step.

How do I go about monsters and players knowing about each other as the gameplay happens? I have no idea what sort of data structures I'd use or how I'd spawn monsters and have them wandering around in zones.

Note: I've seem mentions of using some sort of tree structures (quad trees) but I don't really understand how they would be applied.

Answer 1

To start, you should just make a list of monsters for each zone. Or a deque, or whatever data structure that suit you, it basically need to be linear, allow both random and linear access, and allow deleting from arbitrary places in case you delete the dead monsters (if you don't delete, this is not needed for example).

Each monster would just search the list within this zone for other monsters and players, and track them this way.

Inefficient? Yes.

A good solution? Depends on the number of entities on the zone (if there are not like 1 million entities, the loops are not that bad, specially on PC or other powerfull platform).

If you are striving for the fastest solution, then go for a tree structure, but this is rather complex.

Answer 2

A very simple approach would be to represent the game board as a two-dimensional array of integers. You can set and clear individual bits within each element of the array to represent the type of player/monster occupying that tile, as well as other things like terrain type, etc.

Alternately, you could create a base class for all "Actors" in the game, then derive a Player and Monster class from Actor. The base class could keep track of common things like position on the grid. The derived classes could track things that are specific to Players or Monsters.

If you build a "Zone" container class that represents the game zone, it could have methods that would move an actor, locate an actor, etc. Internally, that class wouldn't need to represent the board as a grid - it could just be a list of actors.

Each Actor that you add to a Zone could maintain a reference to the Zone in which it resides. This would allow each Actor to examine the other actors in the zone.

Answer 3

In well known popular game this awareness is implemented as "aggro list". every creature alsways has this list. It is initially empty. Whenever creatures get in aggro proximity, this list is populated. The removal from list happens when some of events reducing aggro happens. Like distance reaches some high limit, or opposite creature dies, does some aggro reducing action etc.

It is good that your design is based on zones, so you can eventually scale the engine to multiple processes/machines. There absolutely should not be any singletons/global structures in scalable engines, or design will fail to scale, when your game will include millions of creatures

Answer 4

I would just map monsters by zones:

Map<Zone, Monster> MonsterByZones = new  Map<Zone, Monster>();

When the character enters a specific zone, i guess the zone should iterate through all of the monsters it contains and ask them to make a decision:

foreach(Monster monster in MonsterByZones[currentZone].Values)
{
    monster.MakeDecision(character);
}

The world should have a method to change the character zone:

world.ChangeZoneIfNeeded(character);

This is a simple way to implement an RPG!

Have fun!

Answer 5

You need to dig deeper into your specification and decide what "knowing about each other" is for. Knowledge alone is meaningless; it's the actions you take based on that knowledge that matter. And the nature of those actions dictates the type of knowledge you need. Generally any single actor can query its world for information about nearby actors as and when it needs to. This information should live outside of the actor in any case.

Answer 6

For a map of regular tiles, you want to use a two dimensional array because it will perform fast random access. Each entry in the array would keep a reference or ID number of the object that exists there (if any). If your objects wants to interact with something on a nearby tile or set of tiles, it should grab the corresponding reference/id from the 2D array entry that corresponds to that tile.

You might use a tree in a game where space is not divided into regular tiles. The tree would partition space into increasingly small areas, and each leaf node would keep a list of references to objects in that area. The tree and the 2D array are both "scene graph" data structures - they keep track of what objects lie in a region of space.