Finding objects

[Krice]

This problem is now present in Teemu also, because I split one object class to subclasses of object types. The problem is that you need then lists and maps for each object type. Lists are ok and can't really be avoided, since you need to store the actual object type somewhere.

But how about maps? The alternative is go through the list when object moves and check if other object is next to it, but it's really slow compared to object pointers stored in a map, where you can get the object handle fast.

One idea I had was go through the list (this is something you do anyway for monsters at least) and record the surrounding objects. That way you can do more complex AI decisions at the same time based on the object type.

I have partially solved some code repeating (in Kaduria) with templates (C++) but it's really just hiding the underlying design.

I wonder if there is some really clever way to do this?

[Etinarg]

I'm not quite sure what the problem is that you need to solve. Maps (hashtables) are usually quick enough for roguelike games so you can just store the object id where you want to reference the object, and then use a map lookup to get the objects data.

I didn't understand the "when an object moves" part though. On the map I have my objects addressed by coordinate, the map then gives me the object id, which then is used as input for the object store, a hashtable. So if the object moves on the map, I just copy the object id from one map cell to the other.

If you want to separate object attributes, you can use different maps (hashtables) to store the different sets of object attributes, that should work well enough.

Edit: I assume I have confused "maps" in the sense of data structures (key based lookup of values) and game maps ... so I added "(hashtables)" where I meant key based lookup, and kept "maps" where I referred to game maps.

Game maps I implement as arrays most often, for the quick lookup by coordinate, or by hashtables which can be similarly quickly accessed by a key derived from the coordinate. For roguelikes with their fixed size map cell, arrays seem best, though.

[ido]

I think we need more background info about your codebase.

I don't really understand what you are trying to do.

What are the lists used for? The maps? Why do you need one for each subclass of "object"?

If I understand you correctly the way I normally do it (in pseudo-java, but the c++ solution should be very similar) is:

Code: [Select]

class Coordinate {
    int x,t;
}

class GameLevel {
    ...
    Map<Coordinate,GameObject> gameObjects= new HashMap<Coordinate,GameObject>();
    // Put objects into map
    ...
    // Check if there is an object at x,y
    if(gameObjects.get(new Coordinate(x,y)) != null)
        //do stuff
    ...
    // do stuff on all objects on the level
    for(GameObject obj: gameObjects.values()) {
        // do something with obj
        ...
    }
}



[ido]

BTW I do something similar but more memory-hungry in c, where instead of a HashMap i use a game_object[map->height][map->width] 2d array for look up and a list of game_objects for iterating on all of them.

The 2d array just holds pointers to the list - that takes sizeof(game_object*) * map width * map height more memory than just using the list alone.

Since sizeof(pointer) is normally just 4 bytes that's not really a significant amount of memory (39kb for a 100x100 map).

[ido]

Edit: I assume I have confused "maps" in the sense of data structures (key based lookup of values) and game maps ... so I added "(hashtables)" where I meant key based lookup, and kept "maps" where I referred to game maps.

I did the same...

I guess the generic term is "associative array" or "dictionary" where as "hashtable" implies a specific implementation?

[Etinarg]

Hashtable is the most common implementation I think. "Associative array" seems to be the more generic term:

http://en.wikipedia.org/wiki/Associative_array

Map seems already specific to C++ or Java ...

http://en.wikipedia.org/wiki/Map_(C%2B%2B)

Ah well. Babylonian confusion of speech, as usual

[ido]

Yes.

Good thing we weren't discussing vectors :p

[Krice]

What are the lists used for? The maps? Why do you need one for each subclass of "object"?

http://koti.mbnet.fi/paulkp/teemu/teemu.htm

You can download the source code. The stuff I'm talking about is in Level class (lists) and then there are item_map and npc_map, both Game_Object type object maps. Now, in the new version Game_Object is derived to creatures and items, and more subclasses are planned (door, obstacle and container). What I try to do is fast way to find out if moving object is hitting some other object. Maps are fast way to do it, but they are another layer of pointers (handles) to object. It would be simple just go through the lists (containers of objects) every time you do something, but it's really slow if you have to do it for each object!

I guess hashmap could be something I'm looking for. I was aware of them, but haven't really used them before. I guess it's time to learn.

[ido]

Yep.

They are among the most versatile and useful data structures you can use, right next to arrays and lists - I use them all the time.

[Z]

Yes, dictionary / associative array are generic terms for this . C++ STL offers "maps" which are implemented using red-black trees, and "hash_maps" which are implemented with hashtables. Maps require items to be comparable (object1 < object2), and always work quite quickly (assuming that you compare quickly), while hashmaps require a hash function, and should work even faster if the hash function is chosen well (that is, it is fast to evaluate it and it rarely returns the same value for different objects), but much slower if it is chosen poorly. Another disadvantage of hashmaps is that they are not supported in some versions of STL, IIRC. Another advantage of maps is that, since they are ordered, you can easily do things like "find all elements with keys between 1000 and 5000".

[Krice]

In this case, what should be used as a key? If it's coordinates of objects then how the hash_map is able to update them when objects move? As they are part of the game object itself.

[Etinarg]

Keys should be constant objects. If the coordinate is the key, and the object moves, you must delete it from the dictionary with the old coordinate and add it again with the new.

Quite similar as if you want to move an entry in an array.

[Krice]

What if you want to go through all objects in the list (hash_map) and move them. Isn't that messing up the list when you delete and then add new items? How can that work? Is someone actually using hash_map in this way? I need a working example.

[Etinarg]

For coordinate lookup I use a 2D array. This gives me an object id. With the id, I can query the dictionary for object data. The object id is constant during object lifetime.

2d coordinate -> 2d array -> object id -> dictionary -> object

If you want the dictionary as map replacement, you need another way to iterate over objects. Maybe keep a list or set of all objects and iterate over that, and use the dictionary only for coordinate based lookup?

[Bear]

I use "actors" to represent game items and monsters.  You can think of it as a base object class for things that have specific locations in the game world. There's a global table of actors that has all the actual data in it.  I look up an actor in that table using its ID number.  The dungeon map is a structure keyed by location, where I look up ID numbers.  So, when I need to know what's on tile XYZ, I query the dungeon map to get its ID, then query the actor table to get its data. 

One complication is that when an actor is being carried, or in a container, its "location" is the actor that contains it or carries it, not a map location.  So this means that when I want to know everything on square XYZ, and I get back a creature!actor or container!actor, I then have to query the actor data itself to get back a list of other actors it's containing/carrying. 

So if the actor on square XYZ is an ogre, I re-query to get a list of what the ogre's carrying.  If one of the things the ogre is carrying is a sack, I re-query to get a list of what's in the sack.  If one of the items in the sack is a box, I re-query to get a list of what's in the box ... and eventually I have a complete list of every actor on that tile.

I decided that it was worth it to put the actor coordinates into the actor data.  It duplicates information, but it makes it possible to query an actor and get its current location, or query a location and get the actor/s on it, without iterating.  An actor's location, in its own data, is either the coordinates of a tile, or a reference to a containing or carrying actor.  It means every time an actor moves (or is contained/carried or uncontained/released) both the actor data and the map have to be updated.  But I have to touch that in a very few routines, and elsewhere I just call those routines, so I never have to worry about it.

There is never a need to iterate over all actors.  At most, I iterate over the actors in a specific area to apply damage when there's an area-effect attack, which I handle as an iteration over map locations.  I guess you're iterating over creature!actors to apply time ticks to them.  I have the schedule as another structure, not too unlike the map, except that instead of querying tile XYZ and getting a list of actor IDs, the schedule allows me to query time XYZ (an integer turn number) and get a list of events that take place during that turn (with real-number absolute times).  Some of these events are monster's turns.  Others are time-keyed events like healing, poison damage, etc.  Any event that needs the ID of an actor has it as part of its data, so I go straight to the actor when it's that actor's turn, rather than finding it in an iteration over all actors most of whose turn it isn't.

Bear