How unit_map should work

Discussion of all aspects of the game engine, including development of new and existing features.

Moderator: Forum Moderators

Post Reply
Dave
Founding Developer
Posts: 7071
Joined: August 17th, 2003, 5:07 am
Location: Seattle
Contact:

How unit_map should work

Post by Dave »

At the moment unit_map is essentially a std::map<location,unit*>. This has issues because any time a WML event is fired, the unit map may be modified, and this can potentially invalidate any iterators into the unit map. Using an invalid iterator can cause the program to crash or do other nasty things.

Forcing the programmer to track every time a WML event is fired and check for invalid iterators puts a lot of pressure on developers.

I propose an alternative scheme:

unit_map should be a class that contains a std::map as a member. It should contain most of the same functions as std::map which it forwards to the std::map member.

The unit_map should contain a 'revision_number' which is the current 'version' of the map. Anytime the unit_map is modified, the revision number is incremented. So, all mutating functions will increment the revision number when they mutate the map.

It should also define its own iterator class, which should behave somewhat differently. The iterator class should contain a std::map::iterator, but also contain a location, a revision number, and a pointer to the map. When the iterator is instantiated, it sets the revision number to the same as the current revision of the map.

Anytime the iterator is accessed -- using operator*, operator++ etc, it checks the revision number of the unit_map. If the revision number is the same as what is held in the iterator, it will simply perform the operation on its member iterator. If the value of the iterator changes, it will also update the location it holds to be equal to the new location the iterator points to.

If, however, the revision number is different in the map to in the iterator, we know the iterator is potentially invalid. In this case, we call find() on the map to search for the location the iterator holds. If find succeeds, the iterator member is assigned to what find() returned. If find() fails, then our iterator is considered invalid. In this case, we throw a unit_map_iterator_invalid exception.

Code that uses the unit_map must catch this exception, but will generally be able to do so in one place, and abort processing. This will be much more usable for developers than simply crashing.

Thoughts on this approach?

David
“At Gambling, the deadly sin is to mistake bad play for bad luck.” -- Ian Fleming
rusty
Inactive Developer
Posts: 21
Joined: January 7th, 2006, 12:26 am

Re: How unit_map should work

Post by rusty »

Dave wrote:At the moment unit_map is essentially a std::map<location,unit*>. This has issues because any time a WML event is fired, the unit map may be modified, and this can potentially invalidate any iterators into the unit map. Using an invalid iterator can cause the program to crash or do other nasty things.

Forcing the programmer to track every time a WML event is fired and check for invalid iterators puts a lot of pressure on developers.
Unfortunately, all we can do is add debugging aids. Code simply cannot cache values across WML events, because they can change *anything*.

Your scheme only addresses unit locations (admittedly the most common change). But even this is insufficient. Consider a WML event on "attack_hits" which changes the defending unit, or swaps it with another unit. The new unit will continue fighting with the old unit's weapon, attacks, etc. (And it will probably error out due to invalid weapon ids). This is a current bug, too.

Perhaps an ideal scheme would propagate unit changes to all structures which care, including battle_context and unit_map. This handles unit changes. In addition, a "bool same_unit(location)" unit map helper would allow code like attack() to know to abort the fight. A WML event which kills a unit, of course, must not actually delete it. (refcounts? gc? handwave?)

I like the idea of catching errors and the exception, but I don't think transparently grabbing a new unit just because it's in the old location is a good idea. Consider subtle bugs like:

hp = unit_map_iter->hitpoints();
... <event replaces unit magically here>
unit_map_iter->set_hitpoints(hp - 8);

(I don't know that anyone does this, but it's another example of value caching).

Hope that feeds debate!
Rusty.
Darth Fool
Retired Developer
Posts: 2633
Joined: March 22nd, 2004, 11:22 pm
Location: An Earl's Roadstead

Post by Darth Fool »

Personally, I think if the unit changes location, or a new unit is put into an old unit's location, it is better to have the iterator find where the old unit has moved to than to have it find the new unit occupying the same location. This could be done using the description tag (or an index associated with it) as a genuine unique ID (will need some minor modifications, as currently the description is only a probably-unique ID). An iterator would store the description(or its index) of the unit instead of its location. If the unit is moved or changed by a WML event, then the iterator still points to the same unit. If the unit is killed, the unit would not be destroyed immediatly, but moved to a graveyard of sorts. The unit would only get destroyed if all iterators that referenced it were destroyed. Or, we could even keep the graveyard around permanently, only pruning units that are explicitly removed by a WML event and only if there are no hanging iterators pointing to it.

I think that this would actually address Rusty's corner case. It would have as a potential bug that depending in what order effects were processed, you could have an effect which is meant to effect only adjacent units ends up effecting a unit that just teleported some other place, but I think that could be avoided. I am probably missing something obvious but that is my first gut reaction.
Dave
Founding Developer
Posts: 7071
Joined: August 17th, 2003, 5:07 am
Location: Seattle
Contact:

Post by Dave »

Okay, an ammendment to accomodate rusty's issue.

Give every unit a unique ID. (I will leave out implementation details for now).

Leave things as I described, however the iterator also holds the ID of the current unit as well as the location. When we do the find() on the map we check the ID is equal. If the find() failed, or if the ID is not equal, then we do a linear search through the map for the unit with the same ID.

If we still can't find the unit, we know it must have been destroyed, and so we then invalidate the iterator and throw an exception.

David
“At Gambling, the deadly sin is to mistake bad play for bad luck.” -- Ian Fleming
User avatar
Sapient
Inactive Developer
Posts: 4453
Joined: November 26th, 2005, 7:41 am
Contact:

Post by Sapient »

I'd like to propose something like this

Code: Select all

class unit_map {
private:
  //for location-based lookup
  std::map<gamemap::location, shared_ptr<unit> > units_by_loc_;

  //for fast identity lookup
  typedef Uint32 unit_count_type;
  //vector of size units_constructed_count
  std::vector< shared_ptr<unit> > units_by_internal_ID_; 

  //for fallback identity lookup
  shared_ptr<unit> unit_by_unique_description(std::string);
public:
  class unit_accessor {
    virtual unit operator->() = 0;
    virtual bool null() = 0;
    virtual operator++() = 0;
    private:
      unit_by_loc::iterator u_;
      Uint32 mutation_count_;
      void refresh();
   }
   unit_accessor find( ... );   
   erase, etc...
}
The way I see it, there are three types of unit accessors needed:

Type 1) a unit accessor that only wants to keep pointing to the same unit based on unique identity
Type 2) a unit accessor that is picky about BOTH location and the unique identity (this is, in my opinion, the most common case)
Type 3) a unit accessor that only wants to keep pointing to the (volatile) unit at a given location. Probably the least common case.

Defining a term:
Unique identity here would ultimately be determined by the unit's unique_description() which is already implemented and is preserved across WML store/unstore operations (although if we had an integer unit_count ID in the C++, hidden from the WML, we would obviously check that first for a speed gain)

Refresher Callbacks:
If, for whatever reason, you want need to maintain a private cache of weapon statistics instead of using the unit_accessor directly, there could be a way of setting a refresh function callback that would refresh your private structure automatically whenever the unit accessor detects a unit change.

Exception handling:
If we forget to handle unit_accessor.null() and try to access the unit anyway, the code should throw an appropriate exception and print a warning to the log.
Type 1) throws unit_dead_exception
Type 2) throws no_unit_at_location or unexpected_unit_at_location, depending on cause
Type 3) throws no_unit_at_location

- - --- - - - - --
Plan B:
Although I think Plan A is the direction we should be headed, I realize it's a tall order and I have a Plan B that would fit pretty much as-is within the existing framework. In this case you would just insert some checks of game_events::mutations() inside the existing unit_map::iterator (which would effectively implement the Type 3 accessor detailed above).
Last edited by Sapient on June 13th, 2007, 12:41 am, edited 2 times in total.
http://www.wesnoth.org/wiki/User:Sapient... "Looks like your skills saved us again. Uh, well at least, they saved Soarin's apple pie."
rusty
Inactive Developer
Posts: 21
Joined: January 7th, 2006, 12:26 am

Post by rusty »

Dave wrote:Okay, an ammendment to accomodate rusty's issue.

Give every unit a unique ID. (I will leave out implementation details for now).

Leave things as I described, however the iterator also holds the ID of the current unit as well as the location. When we do the find() on the map we check the ID is equal. If the find() failed, or if the ID is not equal, then we do a linear search through the map for the unit with the same ID.

If we still can't find the unit, we know it must have been destroyed, and so we then invalidate the iterator and throw an exception.

David
I'm not sure we want the fight to continue if the unit is teleported away.

How about a superset of this:
1) Put the location in the unit itself, like any other attribute.
2) unit_map is then just an accelerator.
3) Put 'killed' as an attribute in the unit, too.
4) Add set_exception_changes() to unit which can sets which attributes throw an exception when changed.

The fight code than then do (pseudo-code):

attacker.set_exception_changes(unit_flags::KILLED, unit_flags::LOCATION, unit_flags::WEAPON);
defender.set_exception_changes(...);

try {
...
} catch()
...
attacker.unset_exception_changes(...);
defender.unset_exception_changes(...);

Thoughts?
Rusty.
User avatar
Sapient
Inactive Developer
Posts: 4453
Joined: November 26th, 2005, 7:41 am
Contact:

Post by Sapient »

rusty wrote:I'm not sure we want the fight to continue if the unit is teleported away.
Agreed. That's why I said the Type2 unit accessor is not the most common desired.
rusty wrote: How about a superset of this:
1) Put the location in the unit itself, like any other attribute.
2) unit_map is then just an accelerator.
3) Put 'killed' as an attribute in the unit, too.
4) Add set_exception_changes() to unit which can sets which attributes throw an exception when changed.

The fight code than then do (pseudo-code):

attacker.set_exception_changes(unit_flags::KILLED, unit_flags::LOCATION, unit_flags::WEAPON);
defender.set_exception_changes(...);

try {
...
} catch()
...
attacker.unset_exception_changes(...);
defender.unset_exception_changes(...);

Thoughts?
Rusty.
I guess my experience as a WML coder has jaded me against the possibility of having a single unit instance correspond to each logical unit. For example, whenever a unit advances or is deserialized, a new instance is created. There are also places in the code where multiple instances of the same unit exist in the same scope. It seems like this could introduce more potential errors than it removes, unfortunately, though I agree it is a tantalizing notion to have the unit aware of all these sorts of changes.

Another disadvantage to that approach is that the unit class is already quite bloated with information, and this would only add more data that we are (usually) not interested in, or when we are interested in it our type of interest may vary across several overlapping scopes.
http://www.wesnoth.org/wiki/User:Sapient... "Looks like your skills saved us again. Uh, well at least, they saved Soarin's apple pie."
SkeletonCrew
Developer
Posts: 787
Joined: March 31st, 2006, 6:55 am

Post by SkeletonCrew »

In general I'd like to see the unit_map being smarter and produce more debug info upon errors, since it has caused quite some bugs.

Personally I think Sapient's solution idea is a the best approach since unit swapping on location also happens and as rusty said that causes bugs. (And I've seen bugs caused by it.) Also WML coders get more and more creative in what they try to do...

@sapient:
Why use std::vector< shared_ptr<unit> > units_by_internal_ID_; instead of a std::map?

About shared_ptr, are you thinking about the boost::shared_ptr? I'm in favour of that :) (I do prefer to use boost::shared_ptr and not std::tr1::shared_ptr since the latter is quite new in not in all distros yet.)

Do you also want like Sirp keep a revision number in an iterator? I do like that idea seems simple and effective and can do some caching.
User avatar
Sapient
Inactive Developer
Posts: 4453
Joined: November 26th, 2005, 7:41 am
Contact:

Post by Sapient »

SkeletonCrew wrote:In general I'd like to see the unit_map being smarter and produce more debug info upon errors, since it has caused quite some bugs.
agreed.
SkeletonCrew wrote: @sapient:
Why use std::vector< shared_ptr<unit> > units_by_internal_ID_; instead of a std::map?
umm... premature optimization? you caught me there. :)
SkeletonCrew wrote: About shared_ptr, are you thinking about the boost::shared_ptr? I'm in favour of that :) (I do prefer to use boost::shared_ptr and not std::tr1::shared_ptr since the latter is quite new in not in all distros yet.)
While we could tie in boost for that, it's not hard to write our own shared_unit_ptr class either. I already did something similar for tracking sound chunk usage. Really, that's just an implementation choice. We could probably use a plain old unit* instead, if desired.
SkeletonCrew wrote: Do you also want like Sirp keep a revision number in an iterator? I do like that idea seems simple and effective and can do some caching.
Yes, that's how the unit_accessor knows that it needs to perform an internal refresh (and call all refresh handlers, if any have been passed in). When the unit_accessor is first constructed it stores the count of game_event::mutations(), then when that number increases, it assumes that the unit may have changed in some way and the internal iterator also needs to be re-located. I have updated my

Code: Select all

 above to show that stuff.
http://www.wesnoth.org/wiki/User:Sapient... "Looks like your skills saved us again. Uh, well at least, they saved Soarin's apple pie."
Post Reply