Temple of The Roguelike Forums
Development => Programming => Topic started by: Krice on June 30, 2010, 08:19:08 AM
-
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?
-
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.
-
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:
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
...
}
}
-
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).
-
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?
-
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 ;D
-
Yes.
Good thing we weren't discussing vectors :p
-
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.
-
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.
-
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".
-
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.
-
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.
-
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.
-
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?
-
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
-
My implementation is similar to Bear's (excluding items):
Each area has a list of Actors (base class for Monster and Player), that is only iterated through if I need to find monsters within FOV (for ranged targeting) or other such effects.
For collision, I have each map Tile point to its Actor, null if none (only one Actor per tile). Similar to Hajo's approach, since the tiles are stored in a 2D array by coordinate, this allows for quick collision checks (passable = tile.isPassable && tile.actor == null) and the ability to draw a map by iterating through tiles and not having to iterate through any external monster/item list.
The downside to this approach is, of course, that when an Actor moves (Actors keep track of their x and y), it must notify the map so that the reference can be removed from the previous tile and placed on the new one. Minor, considering the benefits.
Hope this helps!
Ebyan "Nolithius" Alvarez-Buylla
http://www.nolithius.com
-
And don't be afraid to have the same thing listed in multiple places. How else would you make an efficient list of Object->Doors without having a list (not a linked list) of all objects and a list of all doors. C++ std::maps are good, I use them for almost everything. If you delete objects, or remove them or save them to an off-screen map, you can keep an std::list of recently deleted numbers for your map to reuse before going on to NUM_ITEMS_IN_MAP +1 or however you manage your global lists of objects. And only use linked lists when they are appropriate and useful for the problem at hand, like if you want things to be in a specific order or if it doesn't matter if you need to get something that is located in the middle of the list. Check out all of the std:: things and see what does what and what is appropriate in which situations - a lot of the boost:: stuff is good too.
-
Another question, actually related to object finding. Let's say the player pushes a large boulder on water. How to check and destroy the boulder? If you need to check the entire list of boulders then it could become slow. How this is usually done? I was thinking of some kind of "destroy list" to add the object, then go through that list and destroy object after everything else is done in a turn.
-
I was thinking of some kind of "destroy list" to add the object, then go through that list and destroy object after everything else is done in a turn.
I did that in some projects. It also works to mark the objects as "to be destroyed" and go through the list of objects after a turn. In my roguelike projects there are seldom more than a few dozen objects on a level, so that is still fast enough to be checked each turn.
You can skip the check on turns when no object was flagged. You can track that separately in a simple boolean.
-
You can skip the check on turns when no object was flagged.
I think that's a good solution, because destroying objects happens rarely so going through the list doesn't make the basic strolling slow.