pedantic object oriented question

[joeclark77]

I'm trying to be a good object-oriented programmer, but I'm self taught and maybe some of you with more book-learnin' have a better grasp of the principles.  One thing that has me stumped is this question: is it OK, I mean according to good practice, to have an object contain a reference to the thing that holds it?  It seems like that would violate some key design principle, but I'm not sure how to do it better.

Here's the specific case:
I have a map object that keeps track of all the Critters (monsters/npcs) and Things (inanimate objects) by their locations.
Critter objects each have an inventory (a python list containing references to Thing objects they're carrying).

This is what I think I'm doing wrong:
Critter objects also have references back to the map that contains them (and to the location that is their index).
Each Thing object has a reference either to the map and location, or to the critter (if carried).

But sometimes you want to look at the map and see what is present in a given location; other times you want to start from the npc or object and find out where it is located.  What would be the proper object oriented way to do this?  I know that this is a pedantic and unnecessary question, but learning a thing or two about programming is indeed why I'm making a roguelike, so, I'm asking anyway!

 

[george]

No, I think the question is a good one. Here's my take on it.

It's best to minimize how spread out your data is across your code, and keep things general. So for example, I would not have references pointing backward (a Critter knowing which map it's in), only forward. A map has a list of levels, a level has a list of things, each thing has a list of their things, etcetera. You can see that this is very general -- everything is a thing, and they can contain other things.

Then for the cases where you want to look at the map and see what's where, or look at a thing and see where it is, I would write the appropriate methods/functions.

It's true that if you want to ask a thing where it is, you need to do a lookup in a more roundabout way than simply querying a property on the thing (though the complexity is well hidden by the method/function anyway). But I would argue that most of the time this will not be a performance critical part of your code. If it is, you can always optimize. Ultimately I think this approach has benefits for OO concepts like reusability, encapsulation and minimizing inter-dependencies.

[guest509]

  I sometimes do that, but it ends up seeming very hacky. It's probably better just to run a check for when you need to know what contains the object rather than updating object.

  I've used it with bullet properties. The bullet has properties based on who shot it, and you also need to know who shot it for the message system. "Yer shot by the Pirate" or "The Captain shoots you." With multiple shooters you start needing a reference variable attached to the bullet. Of course this would have been alleviated by not even making a bullet, and simulating the hit, but I actually checked line of sight and trajectory by running the projectile through every intervening square...anyway...:-)

  Maybe that's not similar, maybe it is, what I ended up doing was doing referencing back up the chain.

[Eben]

For my 7dRL I tried having the map have an array of map cells and also a list of creatures on the map. Each creature also knows it's own location, but only as a point not in reference to the actual map. This allows me to easy run through the list of creatures and do distance calculations without referring to the map cells and then find the cell with the creature I'm working with without having to iterate the map.

Note that Map has ArrayList<Creature> and MapCell[][], MapCell has Creature, and Creature has Point. No circular dependance, no OO principle breaking. The only thing to watch out for is to update the creature's Point when you move it to a new map cell, which is no big deal.

[Krice]

I think the array of map cells can be thought as a container of objects, but I think it's not useful in that task, because you need to iterate through the entire map to search for objects. I guess it's better use a list for objects owned by level class and then use map array as some kind of temporary "copy" of object handles (pointers). You can then access objects from that handle and even use map in things like collision checking, but still retain the ownership of object in the level class. I think the ownership is the important issue, because it's pedantic if only one host can own the object and take care of its creation and destruction.

[joeclark77]

I'm using Python dictionaries (other languages call them "hashes") to locate things on my map.  There are three so far:

terrains = [an array containing a reference to one terraintype per map tile]
things = a dictionary, indexed by tile number, pointing to a list (stack) of items at that tile
critters = as 'things' but for critters

A dictionary is good for a "sparse array".  For example, if my map has 1000 tiles, the list of terrains will be 1000 items long.  But if there's only one "critter" (i.e the player) and he's at tile 345, the 'critters' dictionary will look like this:
{345:<Critter object>}
So you don't have to iterate over 1000 map cells to figure out what your critters are doing.


I'm also going to make use of "tags" for things, critters, etc.  So a torch or lantern might have the tag [illuminating].  There will also be a dictionary indexed by tag, each entry containing pointers to the objects with that tag.  So if I want to run a function on my light sources, I don't have to iterate between the thousands of inanimate objects in the game, just iterate through the [illuminating] set.

The trick is, if I get a pointer to a torch in this way, how do I then get its location (or its carrier's location) so I can implement its effect?  Iterating around all map cells and all critters would eliminate the efficiency gains.  Maybe my hacky way of having the objects point back to their containers is actually going to be the least problematic.

By the way, I'm trying to do a real-time simulation game (kinda like dwarf fortress but not) which is part of why I'm pushing for efficiency.

[george]

I guess I would just ask you this: do you know that iterating over a 1000 objects vs. 2 is a real efficiency gain?

Why not mock up a list of 1000 objects and a list of two and then time the iteration?

That said, I don't think many games would iterate over every map cell to deal with a thing. On the other hand, most games would not subdivide their things into many data structures either.

[joeclark77]

I guess I would just ask you this: do you know that iterating over a 1000 objects vs. 2 is a real efficiency gain?

Why not mock up a list of 1000 objects and a list of two and then time the iteration?

That said, I don't think many games would iterate over every map cell to deal with a thing. On the other hand, most games would not subdivide their things into many data structures either.

No, I don't know if it's a huge difference.  I'm only deducing it.  Hard to test, at this point, because my "things" don't really do anything yet.  But, if I'm going to have a huge map with thousands of things, where most are just sitting around but a few of them are performing actions, I don't want to try and iterate (30 times per second?) over the thousands of things and test each one's thing-type before running a function.

I *have* observed a similar finding in my code that draws the map to screen.  The initial screen-draw requires iterating over every tile and rendering it as a sprite.  Subsequent draws grab a list of "changed tile" indexes and re-render only those tiles (rather than iterating over every tile and re-rendering or checking whether it needs to be re-rendered).  This is fantastically faster.

[Krice]

The trick is, if I get a pointer to a torch in this way, how do I then get its location (or its carrier's location) so I can implement its effect?

The item or monster should have a location stored in it. I think you are doing things over-complicated way. Let's say a monster is carrying a lit torch. The torch location doesn't have to be updated, because the monster is carrying it. The torch needs only know it's lit. When you draw the monster you check if it has a torch in its light slot (faster than looking through the inventory) and then update the light map from monster's location. I think it's easiest to model things like they are: when monster picks up an item it's stored in monster's inventory/tool slot and the monster becomes the owner of the item. The item doesn't have to be anywhere else or referenced in any other place.

[Omnomnom]

I do:
Every tile on the map has a reference to the map, a reference to the creature inhabiting the tile and a reference to the item on the floor of the tile. Each creature references the tile it is on. You can get the map a creature is on through creature->tile->map.

So everything is accessible from everything directly. The only danger is things falling out of sync, but as long as you have methods like creature.moveto(tile) which guarantee everything is fixed and only go through those methods everything is fine.

[requerent]

Object-oriented design and video games aren't really the most logical fit in a conceptual sense. Strong type systems and inflexible hierarchies tend to get in the way of your ability to express what you want. You find yourself going back and fixing objects that result in cascading changes in how everything is done. This contradicts the idea of what a video game really is-- Nested tables of data, a collection of looping systems, and a UI.


There are bigger questions here though if you go the OO route. I always got buggered out because I could never really decide where methods should be and what objects should have access to what data. For ease of implementation, letting everything reference everything is a good way to get OO-principles from blocking your progress. This is bad OO, but I'm starting to hate OO to the point of trolling anyone who mentions it.

But yea- you want to be able to access WorldInfo from every actor in that world. All Actors (including wall tiles) should inherit from an actor base class with events like onBumped, onTick, and other junk that everyone overwrites so that everything can communicate with each other in a hunky-dory way. That's how it's done in industry.

Edit: To add- abstractly, all Actors can have a location and an owning Actor. GetLocation() would just return the location of the Owner, if it has one, otherwise it can return it's own location (which would should be set whenever the player drops/throws the item). Alternatively- the Owning Actor can have a set of ownedObjects. Each time the Actor moves, you can iterate through each object and update the position of those objects.

Are you programming in Python? Python has a lot of slick solutions to do this- though Lua, IMO, is infinitely more well-suited... though I wouldn't use traditional hierarchical OOP at all in either case.

[Ex]

Having an object contain a pointer to it's parent object is pretty common (especially in GUI programming). I actually don't use it a lot in roguelikes because most of the time I'm going in the opposite direction, from parent to child, and don't need to know (or I already know) who the parent is. The only thing that it adds is that you have to make sure to keep the parent of each object up to date, but that's pretty simple. If it works for you, use it.

I don't really buy into the concept anymore that anything in programming is better or worse than anything else. If it works, and it works well, and it isn't slow, then it's good. I'm sure everyone else disagrees with that, but it works well for me. The difference between theory and practice with programming is that practice is all about implementing something that works as quickly as possible (or in as small an amount of time as possible). It's much more important that something is implemented and works than that it is implemented "perfectly" or "correctly". The user doesn't know the difference between the two. All the user sees is whether or not something is implemented at all.

If you spend too much time trying to figure out the "perfect" way to do something you're likely to end up over engineering the whole thing, and spending way more time on the problem than it really needed. Nothing needs to be perfect, it just needs to work. In the professional programing world no one talks about perfect solutions, they talk about deadlines and the amount of time it takes to implement things.

[kraflab]

I don't really buy into the concept anymore that anything in programming is better or worse than anything else. If it works, and it works well, and it isn't slow, then it's good. I'm sure everyone else disagrees with that, but it works well for me. The difference between theory and practice with programming is that practice is all about implementing something that works as quickly as possible (or in as small an amount of time as possible). It's much more important that something is implemented and works than that it is implemented "perfectly" or "correctly". The user doesn't know the difference between the two. All the user sees is whether or not something is implemented at all.

I'm not disagreeing, but of course a sloppy yet fast implementation today can easily slow you down later on

[requerent]

I don't really buy into the concept anymore that anything in programming is better or worse than anything else. If it works, and it works well, and it isn't slow, then it's good. I'm sure everyone else disagrees with that, but it works well for me. The difference between theory and practice with programming is that practice is all about implementing something that works as quickly as possible (or in as small an amount of time as possible). It's much more important that something is implemented and works than that it is implemented "perfectly" or "correctly". The user doesn't know the difference between the two. All the user sees is whether or not something is implemented at all.

I'm not disagreeing, but of course a sloppy yet fast implementation today can easily slow you down later on

That is definitely true for OOP, not necessarily true for other paradigms.

[Krice]

It's much more important that something is implemented and works than that it is implemented "perfectly" or "correctly".

People who say that don't get the idea. The principles of OOP were not invented because they are "correct". During the years I have learned to use some of the OOP techniques while I feel there is less need for some others. What I see frequently are programmers who use everything without any good reason. In C++ it's usually overusing templates and inheritance. It's important to really understand OOP and how you can use it in a practical way. I think the difficulty of OOP is one of the reasons why strict OOP languages are not that good in programming real programs and why C++ is so popular, because it's multi-paradigm and you can break strict rules which is sometimes better and faster solution.