Decision Table for the Movement AI in a Game

Question

I posted a question on Stack Overflow about how to implement Decision Tables in Objective-C after reading about them for the first time in chapter 18 of Code Complete. Nobody provided an answer, so after puzzling it out for a while longer, I created the following code for the movement AI of the enemies in my strategy game.

The basic way it works is that there are a number of string constants, one for each value in the enum EnemyMovementState. The dictionary is then filled with these constants as keys, and the string names of methods in the class as objects. Then I run a switch statement that returns the appropriate string constant for the current state, and pull the object out of the dictionary with that key. This is converted into a selector, and the method is called. This replaced the switch statement that previously had a case for each value in the enum.

I truly do not know if there is any advantage to doing things this way. I think that part of the point of decision tables is to be able to input multiple values and determine an outcome based on the combinations of them. This current implementation only handles one input, the state. I think this could be extended to an intermediate method that could take the current state combined with some other values to retrieve other appropriate methods from the dictionary.

The problems I see are that I need all those string constants, and I still need to run a switch over the states of the enum to return the appropriate string to access the dictionary. I would love it if I could directly convert the name of a value of an enum into a string, but I don't know of a way to do this. So even though this functions as a decision table, it still needs a switch statement to work, and needs more supporting code to make the whole thing work. If I used the value of the enum directly, I could avoid the switch statement, but then if I moved the order around inside the enum the code would break, and on the whole this seems less extensible and less understandable. I would love to get feedback on this, including feedback that the whole thing is pointless and that switch statements are better.

#import "DTEnemyMovement.h"
#import "DTTowerFloor.h"

/*
 Each tick something will happen based on the state, or the state will be processed elsewhere
 Towers and Floors both may contain enemies, though they will always be on a floor unless moving between floors
 To update the movement, a method converts the current state to a string, and gets the method name to call from a dictionary
 This works like a decision table and removes the need for a switch statement
 Movement can only be up or down, left or right, no combination of them
 */

//Two options for the decision table, either access the dictionary directly with 0-x, the enum values, or make strings for their names
//the advantage of strings is that it is more extensible, and the position in the enum doesnt matter
NSString* const kEnemyMovementStateJustSpawned = @"enemyMovementStateJustSpawned";
NSString* const kEnemyMovementStateIdle = @"enemyMovementStateIdle";
NSString* const kEnemyMovementStateNeedsMoving = @"enemyMovementStateNeedsMoving";
NSString* const kEnemyMovementStateToFloor = @"enemyMovementStateToFloor";
NSString *const kEnemyMovementStateAtDestinationFloor = @"enemyMovementStateAtDestinationFloor";
NSString* const kEnemyMovementStateToFloorExit = @"enemyMovementStateToFloorExit";
//NSString* const kEnemyMovementStateAtFloorExit = @"enemyMovementStateAtFloorExit"; //tower handles
NSString* const kEnemyMovementStateToAttackWalls = @"enemyMovementStateToAttackWalls";
//NSString* const kEnemyMovementStateAtAttackWalls = @"enemyMovementStateAtAttackWalls"; //floor handles
NSString* const kEnemyMovementStateToAttackFloor = @"enemyMovementStateToAttackFloor";
//NSString* const kEnemyMovementStateAtAttackFloor = @"enemyMovementStateAtAttackFloor"; //floor handles
NSString* const kEnemyMovementStateToAttackRoom = @"enemyMovementStateToAttackRoom";
//NSString* const kEnemyMovementStateAtAttackRoom = @"enemyMovementStateAtAttackRoom"; //floor handles
//NSString* const kEnemyMovementStateStunned = @"enemyMovementStateStunned"; //not yet used


@implementation DTEnemyMovement {
    NSMutableArray *_floorList;

    int _startingFloor;

    NSDictionary *_decisionTable;
}

-(id) initWithWorldSizeForCharacter:(CGSize)worldSize andStartingFloor:(int)startingFloor {
    self = [super initWithWorldSize:worldSize];
    if (self) {
        _floorList = [[NSMutableArray alloc]init];
        _startingFloor = startingFloor;

        _decisionTable = [[NSDictionary alloc]init];
        [self setupDecisionTable];
    }
    return self;
}
-(void) setupDecisionTable {
    //the string objects are the names of methods in the class
    _decisionTable = @{kEnemyMovementStateJustSpawned: @"doEnemyJustSpawned",
                       kEnemyMovementStateIdle: @"doEnemyIdle",
                       kEnemyMovementStateNeedsMoving: @"doEnemyNeedsMoving",
                       kEnemyMovementStateToFloorExit: @"doFloorMovement",
                       kEnemyMovementStateToFloor: @"doVerticalMovement",
                       kEnemyMovementStateAtDestinationFloor: @"doEnemyAtDestinationFloor",
                       kEnemyMovementStateToAttackWalls: @"doFloorMovement",
                       kEnemyMovementStateToAttackFloor: @"doFloorMovement",
                       kEnemyMovementStateToAttackRoom: @"doFloorMovement"
                       };
}
-(NSString *) stringForState:(EnemyMovementState)state {
    switch (state) {
        case EnemyMovementStateJustSpawned:
            return kEnemyMovementStateJustSpawned;
        case EnemyMovementStateIdle:
            return kEnemyMovementStateIdle;
        case EnemyMovementStateNeedsMoving:
            return kEnemyMovementStateNeedsMoving;
        case EnemyMovementStateToFloor:
            return kEnemyMovementStateToFloor;
        case EnemyMovementStateAtDestinationFloor:
            return kEnemyMovementStateAtDestinationFloor;
        case EnemyMovementStateToFloorExit:
            return kEnemyMovementStateToFloorExit;
        case EnemyMovementStateAtFloorExit:
            return nil;
        case EnemyMovementStateToAttackWalls:
            return kEnemyMovementStateToAttackWalls;
        case EnemyMovementStateAtAttackWalls:
            return nil;
        case EnemyMovementStateToAttackFloor:
            return kEnemyMovementStateToAttackFloor;
        case EnemyMovementStateAtAttackFloor:
            return nil;
        case EnemyMovementStateToAttackRoom:
            return kEnemyMovementStateToAttackRoom;
        case EnemyMovementStateAtAttackRoom:
            return nil;
        default:
            break;
    }
    return nil;
}

#pragma mark - Update Loop
-(void) doMovement {
    //the selector is formed from a string inside the decision table dictionary
    SEL methodToCallName = NSSelectorFromString([_decisionTable objectForKey:[self stringForState:self.state]]);
    if (methodToCallName) {
        IMP functionPointer = [self methodForSelector:methodToCallName];
        void (*methodToCall)(id, SEL) = (void *)functionPointer;
        methodToCall(self, methodToCallName);
    }
}
-(void) doEnemyJustSpawned {
    if ([self checkFloorsForJobs]) {
        self.state = EnemyMovementStateNeedsMoving;
    } else {
        self.state = EnemyMovementStateIdle;
    }
}
-(void) doEnemyIdle {
    if ([self checkFloorsForJobs]) {
        self.state = EnemyMovementStateNeedsMoving;
    } else {
        [self doIdleMovement];
    }
}
-(void) doEnemyNeedsMoving {
    [self calculateFloorExitPositionByFloor];
    self.state = EnemyMovementStateToFloorExit;
}
-(void) doEnemyAtDestinationFloor {
    BOOL foundADestination = NO;
    for (DTTowerFloor *floor in _floorList) {
        if (floor.floorNumber == self.currentFloor) {
            //attack room first, then walls, then bottom
            if (floor.floorBuildState & FloorHasRoom) {
                [self moveToAttackRoom];
                foundADestination = YES;
            } else if (floor.floorBuildState & FloorHasWalls) {
                [self moveToAttackWalls];
                foundADestination = YES;
            } else if (floor.floorBuildState & FloorHasBottom) {
                [self moveToAttackBottom];
                foundADestination = YES;
            }
        }
    }
    if (!foundADestination) {
        self.state = EnemyMovementStateIdle;
    }
}
-(void) moveToAttackBottom {
    [self pickRandomDestinationOnCurrentFloor];
    self.state = EnemyMovementStateToAttackFloor;
}
-(void) moveToAttackRoom {
    [self pickRandomDestinationOnCurrentFloor];
    self.state = EnemyMovementStateToAttackRoom;
}
-(void) moveToAttackWalls {
    //decide which wall to move to, the nearest one
    int positiveOrNegative = 0;
    if (self.currentPosition.x >= 0) {
        positiveOrNegative = 1;
    } else {
        positiveOrNegative = -1;
    }

    //move to the left or right wall
    self.destinationPosition = CGPointMake(([self worldSize].width / 2.1) * positiveOrNegative, self.currentPosition.y);
    self.state = EnemyMovementStateToAttackWalls;
}
-(BOOL) checkFloorsForJobs {
    NSMutableSet *floorsInRange = [[NSMutableSet alloc]init];

    for (DTTowerFloor *floor in _floorList) {
        if (floor.floorNumber == _startingFloor || floor.floorNumber == _startingFloor - 1 || floor.floorNumber == _startingFloor + 1) {
            if (floor.floorBuildState & FloorHasWalls) {
                [floorsInRange addObject:floor];
            } else if (floor.floorBuildState & FloorHasBottom) {
                [floorsInRange addObject:floor];
            } else if (floor.floorBuildState & FloorHasRoomUpgrade) {
                [floorsInRange addObject:floor];
            }
        }
    }

    if (floorsInRange.count > 0) {
        NSMutableArray *tempArray = [[NSMutableArray alloc]init];
        for (DTTowerFloor *floor in floorsInRange) {
            [tempArray addObject:floor];
        }
        self.destinationFloor = [self closestFloor:tempArray];
        return YES;
    }

    return NO;
}

#pragma mark - Overrides
-(void) arriveAtDestinationFloor {
    self.currentPosition = self.destinationPosition;
    self.currentFloor = self.destinationFloor;
    self.state = EnemyMovementStateAtDestinationFloor;

     //not sure if this conditional is needed but it is good for debugging
     if (self.state == EnemyMovementStateToFloor) {
         self.state = EnemyMovementStateAtDestinationFloor;
     }
}
-(void) doFloorMovement {
    //once close enough to the destination, jump to the destination
    if ([self isAtFloorDestinationPosition]) {
        self.currentPosition = self.destinationPosition;
        if (self.state == EnemyMovementStateToFloorExit) {
            self.state = EnemyMovementStateAtFloorExit;
        } else if (self.state == EnemyMovementStateToAttackWalls) {
            self.state = EnemyMovementStateAtAttackWalls;
        } else if (self.state == EnemyMovementStateToAttackFloor) {
            self.state = EnemyMovementStateAtAttackFloor;
        } else if (self.state == EnemyMovementStateToAttackRoom) {
            self.state = EnemyMovementStateAtAttackRoom;
        }
    } else {
        if ([self shouldMoveRight]) {
            [self moveRight];
        } else {
            [self moveLeft];
        }
    }
}

#pragma mark - Floor List
-(void) acceptFloorList:(NSMutableArray *)floorList {
    _floorList = floorList;
}

#pragma mark - NSCoding methods
-(id) initWithCoder:(NSCoder *)aDecoder {
    self = [super initWithCoder:aDecoder];
    if (self) {
        _state = [aDecoder decodeIntegerForKey:@"enemyMovementState"];
        _floorList = [aDecoder decodeObjectForKey:@"floorList"];
        _startingFloor = [aDecoder decodeIntForKey:@"startingFloor"];
        _decisionTable = [aDecoder decodeObjectForKey:@"decisionTable"];
    }
    return self;
}
-(void) encodeWithCoder:(NSCoder *)aCoder {
    [super encodeWithCoder:aCoder];
    [aCoder encodeInteger:self.state forKey:@"enemyMovementState"];
    [aCoder encodeObject:_floorList forKey:@"floorList"];
    [aCoder encodeInt:_startingFloor forKey:@"startingFloor"];
    [aCoder encodeObject:_decisionTable forKey:@"decisionTable"];
}

@end

Answer 1

-(id) initWithWorldSizeForCharacter:(CGSize)worldSize andStartingFloor:(int)startingFloor;

It's slightly better to use instancetype as the return type here rather than id. What we're actually returning (here) is a DTEnemyMovement object, but explicitly listing this as the return type is problems when subclassing because we're returning the super type instead of the subclass's type.

Using id prevents that problem, but id is just a generic object pointer that the IDE can do no type-checking on. It wouldn't give us a warning if we tried assigning the return from this method into a UIButton object, for example (but it would lead to trouble eventually).

Meanwhile, instancetype is the best of both worlds. It will provide smart type checking, but still be generic and return the appropriate type based on whether it's this class or some subclass.

Beyond the return type, the method name needs some work. There are 3 words that are misleading and confusing. ForCharacter and and don't belong in this method name.

First of all, ForCharacter. What character? Perhaps the result is used for a character, but the method doesn't care how its result is used and it's name shouldn't indicate how its result is supposed to be used. The method name should indicate what the method does and with what parameters.

And and is only used in method names to indicate multiple actions and never used to indicate multiple arguments. The number of arguments is rarely confusing... since they all have names.

So truly, the method name should look like this:

- (instancetype)initWithWorldSize:(CGSize)worldSize startingFloor:(int)startingFloor;

---

One final note about this method, I'm not sure if you're aware of these class methods or not, but rather than alloc] init], you can just do:

[NSMutableArray array];
[NSDictionary dictionary];

Methods like this exist for numerous Objective-C classes as well. I personally prefer this to alloc] init];

Answer 2

-(void) setupDecisionTable;

I was going to recommend declaring constants for the strings you're adding into the dictionary here, but there's a better way.

First though, let's change this to a class method that returns a dictionary rather than an instance method that touches an instance variable.

+ (NSDictionary *)decisionTable;

And to be honest, we don't truly need an instance variable to store this information in, do we? We can just call this method when we need this variable, and there's a good way to let every instance of the class use the same dictionary (which should be perfectly fine since it's immutable).

First, a static method variable which we'll return:

+ (NSDictionary *)decisionTable {
    static NSDictionary *decisionTable;

    return decisionTable;
}

Now we need to initialize it, and to do so, let's use the inverse of NSSelectorFromString:

+ (NSDictionary *)decisionTable {
    static NSDictionary *decisionTable;

    if (!decisionTable) {
        decisionTable = @{kEnemyMovementStateJustSpawned:NSStringFromSelector(@selector(doEnemyJustSpawned)),
            // ... etc...
        };
    }

    return decisionTable;
}

This works mostly fine, but there could be trouble if there's every any multithreaded access, so let's fix that with a @synchronize:

+ (NSDictionary *)decisionTable {
    @synchronized(self) {
        static NSDictionary *decisionTable;

        if (!decisionTable) {
            decisionTable = @{kEnemyMovementStateJustSpawned:NSStringFromSelector(@selector(doEnemyJustSpawned)),
                // ... etc...
            };
        }

        return decisionTable;
    }
}

Only one thread is allowed within the @synchronized block at a time. Any others will wait until the thread in front of it finishes this block.

Since the dictionary is the same for every class, we've now saved time and memory space by keeping only one copy and sharing it across all instances. Accessing the dictionary by calling this method is just as fast as accessing it through a local variable's getter method.

Other languages such as Java have static class-level variables, and if this were one of those classes, that's what I'd recommend using. But in Objective-C, this is the pattern for emulating a class-level variable: a static local variable in a class-level method.

And don't forget to eliminate the instance variable for your decision table.

Within the class, you can access this dictionary via:

[DTEnemyMovement decisionTable]

OR

[[self class] decisionTable]

With the latter being the better way, in case of subclassing.

Answer 3

-(NSString *) stringForState:(EnemyMovementState)state;

Some comments about this method.

First of all, much like our decisionTable method, there's no reason for this to be an instance method. In this case, the decision is even more clear. We're not using any instance variables, read or write, so we can simply change to a class method without rewriting anything else.

Second of all, the entire point of this method is not to generate a printable string, but rather to generate a key into a dictionary. Objects other than NSString can be used as dictionary keys. In fact, anything that conforms to <NSCopying> protocol can be used, so this should be our real return value--an object conforming to NSCopying.

Third, I'm not sure why you break from default only to return nil. We can just return nil; in default.

Fourth, rather than moving this method from instance to class, we might consider moving it to a function. It fits the same pattern as the NSStringFromSelector() and NSSelectorFromString() functions. So:

id<NSCopying> DTDecisionKeyForMovementState(EnemyMovementState state) {
    switch (state) {
        // stuff
        default: return nil;
    }
}

Answer 4

I want to point out a few small things that can improve the readability:

---

if (floor.floorNumber == _startingFloor || 
    floor.floorNumber == _startingFloor - 1 || 
    floor.floorNumber == _startingFloor + 1)

This spacing already helps the readability without changing anything else, but in plain English, we want to know if floor.floorNumber is the starting floor or an adjacent floor, right? So...

if (abs(floor.floorNumber - _startingFloor) <= 1)

For a starting floor of 10, this returns YES when floor.floorNumber is 9, 10, or 11 and NO for everything else.

---

self.currentPosition = self.destinationPosition;
if (self.state == EnemyMovementStateToFloorExit) {
    self.state = EnemyMovementStateAtFloorExit;
} else if (self.state == EnemyMovementStateToAttackWalls) {
    self.state = EnemyMovementStateAtAttackWalls;
} else if (self.state == EnemyMovementStateToAttackFloor) {
    self.state = EnemyMovementStateAtAttackFloor;
} else if (self.state == EnemyMovementStateToAttackRoom) {
    self.state = EnemyMovementStateAtAttackRoom;
}

There's nothing inherently wrong with this bit of code... but it just seems like we're trying to describe to much with this state. We're describing not just whether or not the entity is in motion, but also, the entity's current or target destination.

The "state" could really only be a few things. In motion, not in motion. Perhaps "paused"? Or "blocked"? These could be states. The rest of what you're describing is the destination or target. In this particular code snippet, we see that the destination or target doesn't really matter.

What matters is that we were traveling to our destination and now we've arrived at our destination. Maintaining a separate traveling and arrived state for every possible target gets really cumbersome in a hurry.

Perhaps it might be time for a Movement struct. The struct should contain at least two members. One describes the movement state, (in motion, paused, blocked, arrived, etc), the other describes the target. And both of the members of the struct should be enums. We just need to separate the target from the destination.

After incorporating the struct, the above code snippet gets turned into this:

self.currentPosition = self.destinationPosition;
self.movement.state = MovementStateArrived;

And we'll never have to add or remove any lines of code if we change the destinations. The destinations are a different struct member which we access in other areas of the code in which the destination is relevant (but the state is not).