Category Archives: Objective-C

Procedural Map Generation In The Lonely Dwarves

The vast majority of places in the world of the Lonely Dwarves is created manually. The Minotaur’s labyrinth however, has two procedurally generated maps for the Dwarves to explore. In addition to being initially random, when they leave and re-enter, a completely new map is created for them.

When I decided to add this feature, I did some careful design work to create something modular and extensible. I hope to reuse large portions of this logic for a roguelike game in the future, while also extending it greatly.

Take a look at the diagram for the basic flow:

Screenshot 2016-03-12 21.44.54

In the Lonely Dwarves, the parameters are specified in an XML file for procedural generation. Take a look at this example, which is currently one of labyrinth levels:

<layout type="random">
  <generators>
    <generator type="maze-grow-tree">
      <size>
        <width>12</width><height>12</height>
      </size>
      <newest>50</newest>
      <random>50</random>
    </generator>
  </generators>
  <translators>
    <translator type="simple-maze">
      <block-width>1</block-width>
    </translator>
    <translator type="fill-border"/>
  </translators>
  <content-creators>
    <content-creator type="hall-treasures">
      <treasure-set id="basic_goodies"/>
    </content-creator>
    <content-creator type="stairs">
      <stair id="initial" to-map="moosecastle_1">
        <destination>
          <coord x="6" y="22"/>
        </destination>
      </stair>
      <stair id="down" to-map="moosecastle_3">
        <destination>
          <target location-id="initial"/>
        </destination>
      </stair>
    </content-creator>
  </content-creators>
  <mapper type="moose-maze"/>
</layout>

The first phase in the process is the generators. It may not surprise you that the internal representation until the very final process is a graph. The generators are responsible for creating the base graph. In the above example there is only a single generator, but they can be chained together to create interesting combinations. The Minotaur labyrinth uses the “simple-maze” generator, and as you can see from the parameters, it is defined to split how it decides what vertex to expand by choosing Prim’s Algorithm 50% of the time and the Recursive Backtracker Algorithm 50% of the time.

The second phase in the process is the translators. The translators process the graph and translate it to a graph that is a better representation of the physical world we’re trying to create. The two translators involved here space the graph so that walls have a thickness (of 1 tile), and insert a border around the graph.

The third phase in the process is the content creators. These examine a graph and add content at locations fitting the parameters. There are currently two content creators for the Labyrinth, one that adds treasures from a predefined collection: ‘basic_goodies’, and the more interesting one, the one that adds stairs. You can see that the stairs have full definitions and ids, they just need a place to go. The content creator will do a search for locations with 3 walls as potential places for stairs and place them randomly in one of the valid locations.

Screenshot 2016-03-12 22.29.32

The final phase is the mapper phase. A mapper looks at the graph and maps it to a … map, sorry for the pun. The graph has a system of identifying what a particular vertex represents, and it’s up to the mapper to make sure that the in game representation matches by using a correct tile and blocking areas that can’t be accessed.

I’m thinking about adding events that turn on lights as you step onto certain tiles to help you navigate. That will be a future enhancement, probably after play-testers get mad that it’s too difficult to traverse the mazes.

Implementing A* in Objective-C like you mean it – Part 4

In the previous article, I showed the implementation for the PSPriorityQueue. That class’s init method creates two data structures, a PSBinaryHeap and a PSHashMirror. See code below:

if(self = [super init]) {
  _heap = [(type == PSPriorityQueueMax) ? [PSBinaryHeap maxHeap]
                                        : [PSBinaryHeap minHeap] retain];
  _mirror = [[PSHashMirror alloc] init];
  [_heap setStorageMirror: _mirror];
}

PSHashMirror is an optional object for a PSBinaryHeap, in order to get the maximum performance from the PSPriorityQueue, we inject one into the PSBinaryHeap instance.

I will describe some of how this class works here. First, let’s take a look at PSBinaryHeap’s insert method.

-(void)insert:(id<PSPrioritized>)item {
  [_storage addObject: item];
  [_storageMirror addObject: (id<PSPriorityNode>)item
                  withIndex: [_storage count] - 1];
  [self _bubbleUp: [_storage count] - 1];
}

Typical for a heap, we insert an object at the end of the internal array, and then invoke the bubble-up portion of the algorithm, which will modify the heap to recreate the heap property. In addition we are also adding the new object to the (optional) PSStorageMirror instance.

-(void)_bubbleUp:(NSUInteger)index {
  NSComparisonResult bubbleComparison =
    _type == PSHeapTypeMin ? NSOrderedDescending
                           : NSOrderedAscending;
  while(![PSBinaryHeap _isTop: index] &&
        ([self _compareParent: index] == bubbleComparison)) {
    NSUInteger parentIndex = [PSBinaryHeap _parentOfIndex: index];
    [_storage exchangeObjectAtIndex: parentIndex withObjectAtIndex: index];
    [_storageMirror updateObject: [_storage objectAtIndex: parentIndex] withIndex: parentIndex];
    [_storageMirror updateObject: [_storage objectAtIndex: index] withIndex: index];

    index = parentIndex;
  }
}

Bubble Up will swap the entry with its parent until the heap property is satisfied. In addition we track the position through the PSStorageMirror.

So now you’re probably wondering where the PSStorageMirror instance helps us. The PSPriorityQueue has methods reprioritize: and reprioritizeIfBetter: which take a node. The PSStorageMirror allows the method to find the index of that node in the heap in constant time. Updating the value and invoking a slightly more specific heapify will reprioritize correctly.

Now we have the most efficient A* implementation that I can think of. Anyone out there have a better way to share?

NSCountedSet or NSCountedWTF!?

NSCountedSet offers a set data structure that keeps track of each time an item is added, and allows the querying of that count.

_simpleCountedSet = [NSCountedSet set];
[_simpleCountedSet addObject: @"Sword"];
[_simpleCountedSet addObject: @"Sword"];
[_simpleCountedSet countForObject: @"Sword"];    // 2

I wanted to recreate the state of an NSCountedSet from a serialized form and found that it lacked the methods to “bulk add” objects or “set count” for an object. This was curious. It made deserializing a silly operation that looked like:

id keyObject = [self deserializeObjectNamed: @"key" fromElement: entryElement];
NSUInteger count = [self deserializeIntegerNamed: @"count" fromElement: entryElement];
while(count--) {
    // This is seriously the only way to do this
    [countedSet addObject: keyObject];
}

If we think about it, what happens if we’re using this to track state and it has … a billion items? To serialize is trivial, just store as pairs of (object, count). To deserialize? Take that count and add object to the countedSet a billion times or so.

I wondered if NSKeyedUnarchiver would do something more efficient. Surely there was a private method or ivar or something that the initWithCoder: method would set.

I designed a unit test to test the relative performance of manually deserializing (looping addObject: calls, as shown above) and using NSKeyedUnarchiver.

I created two NSCountedSets. One with 6 entries totaling 2.85 million count distributed over the 6. One with 6 entries of count 1 each.

First I tested with my manual serialization process.

NSString *complexSerialized = [NSString stringWithFormat: @"<xml>%@</xml>", [PSXMLUtils serializeObject: _complexCountedSet withName: @"complexSet"]];

An xml string representation is created. Serializing for both sets registers at 0.000 seconds, basically unmeasurable time to execute.

Then I deserialized:

PSXMLDocument *doc = [[PSXMLDocument alloc] initWithXMLString: complexSerialized enableXPath: NO];
PSXMLElement *root = [doc root];
deserializedSet = [[PSXMLUtils deserializeObjectNamed: @"complexSet" fromElement: root] retain];

We loaded the xml to a DOM using my libxml wrapper. Then we processed the tree and looped, doing 2.85 million AddObject: calls. The simple case took 0.000 seconds, the complex .212 seconds. Faster than I expected perhaps for 3 million hash lookups and updates? But still concerning. The built in serialization simply has to be faster right?

Here’s how to serialize using NSKeyedArchiver:

NSMutableData *data = [NSMutableData data];
NSKeyedArchiver *arc = [[NSKeyedArchiver alloc] initForWritingWithMutableData: data];
[arc encodeObject: _complexCountedSet forKey: @"complexSet"];
[arc finishEncoding];

A binary representation is created and stored in the object that ‘data’ points to. Time to execute: 0.000 seconds. Super. Fast.

Here’t how to deserialize:

NSKeyedUnarchiver *unarc = [[NSKeyedUnarchiver alloc] initForReadingWithData: data];
unarchivedSet = [unarc decodeObjectForKey: @"complexSet"];

Time to execute: 0.000 seconds for the simple set, 0.212 seconds for the complex one. 4 MS faster than my XML implementation. This leads me to believe that the only methods used to recreate the state of the NSCountedSet are from the public interface. Apple really has code that is forcing 2.85 million AddObject: calls rather than setting the count in one step.

I found this to be pretty silly.

Clang Static Analyzer – Removing False Positives

The Clang static analyzer is fantastic, and I recommend you run it often. Static Analysis is recommended by the best in the industry. Isn’t it annoying when the static analyzer flags things you know are correct?

Here is an example of an array of constants we want to keep around for the lifetime of the application. Using some preprocessor magic tells the static analyzer to ignore the potential issue:

+(void)initialize {
	if(self == [WRVerticalAlignmentEnum class]) {
		s_vertXmlNames = @[ @"top", @"center", @"bottom", @"stretch" ];
#ifndef __clang_analyzer__
		[s_vertXmlNames copy];
#endif
	}
}

Math and Game Design: Damage Filters for Abilities

Tales of Jornica: The Lonely Dwarves will have many weapons, magic spells, and abilities that you can use to vanquish your foes. In order for things to be interesting I have been attempting to design interactions that can be utilized in complex ways. Suppose you have an ability that does damage to a monster. The direct damage is represented by an object that breaks up the potential damage by element and each element has a Calculated Expression associated with it. A Calculated Expression, as described in a previous blog posting, combines dice rolls and custom formulae. Each time an ability is used to cause damage, a roll is invoked on this object and a RolledDamage object is created.

Now suppose your character is wielding a Flame Sword – It does some Physical damage, and a great deal of Fire damage. We are in an environment that magnifies fire damage making it an awesome weapon. The magnification of Fire Damage is accomplished with a Damage Filter – this one in particular is due to an environmental effect. The effect can be described as “Fire Damage is increased by 50%”

Now what happens when we come across a Fire Elemental? Fire damage actually heals those things, we are in trouble! Or are we? We just happen to have a Ring of Bad Imperial to Metric Temperature Conversion. Wearing bestows a damage filter described as “Fire Damage is decreased by 30% and converted to Ice Damage” Awesome! We lose some total damage in the process, but we now can hit the Fire Elemental with an element it is weak against. Victory! Interesting item synergies achieved! Order is important – if we convert all the Fire damage to Ice damage first, then the environmental Fire damage boost is useless. A well defined order of filters is still being thought out.


Example:
Attack the Fire Elemental with our Fire Sword
RolledDamage object shows 100 Fire damage and 20 Physical Damage
Apply the Environment Filter
RolledDamage is now 150 Fire Damage and 20 Physical Damage
Apply the Ring's Filter
RolledDamage is now 0 Fire Damage, 20 Physical Damage, and 105 Ice Damage

So – how do we implement Damage Filters? We need to take the rolled result and in order, apply each filter to it to get the final result. Again, order is important. If we treat the damage roll as a vector, we can use linear algebra to solve this ultra simply, and using Apple’s Accelerate Framework, efficiently. Each filter is a linear transformation that acts on the damage vector – and a very simple representation of a linear transformation is…. a matrix! Once we get our list of filters they can be multiplied in order, and the resulting matrix combines all the filters in one structure. Then we multiply the damage vector and that final matrix and get a new damage vector that is our final result.

Let’s take a look at the matrix representation:

The identity matrix returns the exact same values when multiplied by the vector:
 | 1.0 0.0 0.0 | | Physical |   | 1.0 * Physical  |
 | 0.0 1.0 0.0 | |   Fire   | = |   1.0 * Fire    |
 | 0.0 0.0 1.0 | |   Ice    |   |   1.0 * Ice     |

Each row of the matrix represents the result of an element.
Each column is how one element will affect all other elements.

Example:
Convert all physical damage to ice and increase by 50%
 | 0.0 0.0 0.0 | | Physical |   |      0.0 * Physical        |
 | 0.0 1.0 0.0 | |   Fire   | = |         1.0 * Fire         |
 | 1.5 0.0 1.0 | |   Ice    |   | 1.5 * Physical + 1.0 * Ice |

Notice the first row is all zeros, this results in a zero value for physical.
The 1.5 is in the first column which is the Physical Source column, being in the last row means it will affect the last element, Ice.

In order to create a filter I devised a serialized form consisting of an XML Element for each operation that changes the filter matrix from the identity matrix.

If you look at the example above, “Convert all physical damage to ice and increase by 50%”, we can break this down to two steps. First, the result has to have physical reduced to zero and second, the result has to have 1.5 times the original physical added to ice. We can represent that using this XML:

<damage-filter>
   <!-- Convert all physical damage to ice and increase by 50% -->
   <set source="physical" target="physical" value="0.0"/>
   <set source="physical" target="ice" value="1.5"/>
</damage-filter>

Another example that requires 3 operations is “Convert all physical damage to 50% Poison and 65% Ice.” Let’s look at the XML representation:

<damage-filter>
   <!-- Convert all physical damage to 50% Poison and 65% Ice -->
   <set source="physical" target="physical" value="0.0"/>
   <set source="physical" target="poison" value="0.5"/>
   <set source="physical" target="ice" value="0.65"/>
</damage-filter>

The DamageFilter object is initialized by this block of XML which will first load the identity matrix as it’s model, then run each operation.

The RolledDamage object has a method that will take an array of filters and return a new RolledDamage representing the filtered damage.

Here is a unit test to confirm everything is working:

// Rolled Damage 1 (Physical: 50.0, Poison: 10.0)
SKElementValues values1;
memset(&values1, 0, sizeof(values1));
values1.elementValue[SKElementTypePhysical] = 50.0;
values1.elementValue[SKElementTypePoison] = 10.0;
_rolledDamage1 = [[SKRolledDamage alloc] initWithDamages: values1];



// Given:	Rolled Damage with (Physical: 50.0, Poison: 10.0)
// When:	Filter of "Convert 50% of physical and double to Fire"
// Then:	Final Damage is Physical: 25.0 Fire: 50.0, Poison: 10.0
NSString *filterString = @"<damage-filter>"
@"<set source=\"physical\" target=\"fire\" value=\"1.0\"/>"		// All of physical goes to Fire
@"<set source=\"physical\" target=\"physical\" value=\"0.5\"/>"	// Reduce physical by 50%
@"</damage-filter>";
PSXMLDocument *doc = [[PSXMLDocument alloc] initWithXMLString: filterString enableXPath: NO];
SKDamageFilter *filter = [[SKDamageFilter alloc] initWithXML: [doc root]];
[doc release];
SKRolledDamage *finalDamage = [_rolledDamage1 filterWith: @[ filter ]];
XCTAssertEqualWithAccuracy([finalDamage damageForType: SKElementTypePhysical], 25.0, 0.01);
XCTAssertEqualWithAccuracy([finalDamage damageForType: SKElementTypeFire], 50.0, 0.01);
XCTAssertEqualWithAccuracy([finalDamage damageForType: SKElementTypePoison], 10.0, 0.01);
XCTAssertEqualWithAccuracy([finalDamage damageForType: SKElementTypeIce], 0.0, 0.01);
XCTAssertEqualWithAccuracy([finalDamage damageForType: SKElementTypeHoly], 0.0, 0.01);
XCTAssertEqualWithAccuracy([finalDamage damageForType: SKElementTypeElec], 0.0, 0.01);

The key line being:

SKRolledDamage *finalDamage = [_rolledDamage1 filterWith: @[ filter ]];

That’s how easy it is to use! Now how difficult was it to implement?

Here is the code to RolledDamage – filterWith:

-(SKRolledDamage*)filterWith:(NSArray*)filters {
	if([filters count] == 0) {
		// No filters then just return the same object
		return self;
	}
	
	const SKElementMatrix *a = [(SKDamageFilter*)[filters objectAtIndex: 0] matrix];
	for(NSInteger i = 1; i < [filters count]; ++i) {
		// If there is more than one filter, continue to multiply them together until we get the final matrix.
		SKElementMatrix res;
		SKDamageFilter *filter = [filters objectAtIndex: i];
		const SKElementMatrix *b = [filter matrix];
		vDSP_mmulD(b->matrix, 1, a->matrix, 1, res.matrix, 1, SKElementTypeCount, SKElementTypeCount, SKElementTypeCount);
		vDSP_mmovD(res.matrix, tmp.matrix, SKElementTypeCount, SKElementTypeCount, SKElementTypeCount, SKElementTypeCount);
		a = &tmp;
	}
	
	SKElementValues vals;
	// Multiply the final matrix by our original damage vector and return a new immutable object representing the filtered results.
	vDSP_mmulD(a->matrix, 1, _damages.elementValue, 1, vals.elementValue, 1, SKElementTypeCount, 1, SKElementTypeCount);

	
	return [[[SKRolledDamage alloc] initWithDamages: vals] autorelease];
}

If there is no filter, just return the exact same value. If there is only one filter, multiply the filter matrix and the damage vector, which results in the result vector – return a new object based on the result vector. If there are multiple filters, multiply them together to create the final filter, then multiply by the damage vector.

Implementing A* in Objective-C like you mean it – Part 3

Last time we looked at the interface to our Priority Queue. Here’s the implementation:

@implementation PSPriorityQueue {
  PSBinaryHeap *_heap;
  PSHashMirror *_mirror;
}

+(PSPriorityQueue*)minQueue {
  return [[[PSPriorityQueue alloc] initWithQueueType: PSPriorityQueueMin] autorelease];
}

+(PSPriorityQueue*)maxQueue {
  return [[[PSPriorityQueue alloc] initWithQueueType: PSPriorityQueueMax] autorelease];
}

-(instancetype)initWithQueueType:(PSPriorityQueueType)type {
  if(self = [super init]) {
    _heap = [(type == PSPriorityQueueMax) ? [PSBinaryHeap maxHeap]
                                          : [PSBinaryHeap minHeap] retain];
    _mirror = [[PSHashMirror alloc] init];
    [_heap setStorageMirror: _mirror];
  }
	
  return self;
}

-(void)dealloc {
  [_heap release];
  [_mirror release];
	
  [super dealloc];
}

-(NSUInteger)count {
  return [_heap count];
}

-(id<PSPriorityNode>)dequeue {
  return (id<PSPriorityNode>)[_heap removeTop];
}

-(BOOL)contains:(id<PSPriorityNode>)object {
  return [_mirror indexForObject: object] != NSNotFound;
}

-(void)reprioritize:(id<PSPriorityNode>)node {
  // It looks like the same node, but really the nodes have the same key, different priority
  [_heap replaceObjectAtIndex: [_mirror indexForObject: node] withObject: node];
}

-(void)reprioritizeIfBetter:(id<PSPriorityNode>)node {
  [_heap replaceObjectAtIndexIfBetter: [_mirror indexForObject: node] withObject: node];
}

-(void)enqueue:(id<PSPriorityNode>)node {
  [_heap insert: node];
}

@end

Pretty simple right? It’s basically a wrapper around two separate data structures. The most obvious is a binary heap, which takes care of most of the operations that we need. The operation that it struggles with is the fast reprioritization (due to the linear search required to find the node). I made the choice to have the binary heap expose its implementation. This is typically frowned upon, as it creates a dependency on something other than the interface. If the implementation is changed, or a class created with the same interface, this system can fail. Carefully weigh the pros and cons and consider how these objects are used before doing something like this.

So, the binary heap is backed by an array. This is not an unusual implementation for a binary heap, but is a detail typically we wouldn’t care about. Consider though, if we could quickly find out an object’s index in that array. Then we would be able to reprioritize the object quickly – the only remaining task is the O(log n) bubble operation.

If we can guarantee our entries are valid and efficient for a hash table, we can along side of the binary heap maintain a hash table mapping the object to its current index in the binary heap’s array.

PSBinaryHeap_Hidden.h is introduced

@interface PSBinaryHeap()

-(void)replaceObjectAtIndex:(NSUInteger)index
                 withObject:(id)anObject;
-(void)replaceObjectAtIndexIfBetter:(NSUInteger)index
                         withObject:(id<PSPrioritized>)anObject;

@end

This is an Objective-C trick used often for “protected” members. First, Create a Class Extension in a separate header file. This extension contains the properties and method definitions that we want to be hidden from consumers of the class. Then import the header by implementation files that care about it – in the case of protected members, subclasses. In this case, we’re exposing two methods that the PriorityQueue can use, but no one that wants a normal Binary Heap should know about.

Next time we’ll take a look at parts of the Binary Heap implementation and how the Hash Mirror fits in to create an efficient A* Implementation

Implementing A* in Objective-C like you mean it – Part 2

In my last article I was discussing how to squeeze performance out of a custom A* implementation. We looked at using an NSMutableArray and a CFBinaryHeap for our Open Set. I am now about to suggest a magical data structure that has these properties:

  • Insert has an average case of O(1) and a worst case of O(log n).
  • Remove Best is O(log n).
  • Update Vertex … O(log n).
  •  

    What data structure is it!? It’s a PriorityQueue implemented with a heap and a dictionary. The heap functions as you might expect, but is implemented using an array. Each entry in the heap therefore can be accessed through this array by index. The dictionary is a mapping of the Vertex (key) to index (value). Whenever the heap updates the location of a Vertex, that information also needs to be sent to the dictionary.

    @interface PSPriorityQueue : NSObject
    
    +(PSPriorityQueue*)minQueue;
    +(PSPriorityQueue*)maxQueue;
    -(id)initWithQueueType:(PSPriorityQueueType)type;
    
    -(NSUInteger)count;
    -(id<PSPriorityNode>)dequeue;
    -(BOOL)contains:(id<PSPriorityNode>)object;
    -(void)reprioritize:(id<PSPriorityNode>)node;
    -(void)reprioritizeIfBetter:(id<PSPriorityNode>)node;
    -(void)enqueue:(id<PSPriorityNode>)node;
    
    @end
    

    Before we go into more detail about the implementation of the Priority Queue let’s talk about Test Driven Development. Coding a Data Structure like a Priority Queue lends itself perfectly to Unit Testing. A data structure should be a stand alone component, and should be reusable in many contexts. It also should very clearly be documented on how it should work. Unit testing verifies that the code is correct, but what is less obvious is that simply by being able to be unit tested, you are ensuring the code is an actual stand alone unit.

    In Test Driven Development you are encouraged to write your tests first. This is the first consumer of code. It should be obvious if the interface makes sense based on the fact that it has a real consumer. If other parts of the system are getting pulled in to the testing environment, it’s a sign that maybe the interface hasn’t been carefully thought out, and should be reconsidered.

    Because I want to test my Priority Queue as separate from the rest of the system as possible, I created some unit test only objects in my unit test project. The Priority Queue holds objects that conform to PSPriorityNode (which itself is a PSPrioritized). I will go into more detail about these later, the simple explanation is that a PSPriorityNode is something that goes into a PSPriorityQueue.

    
    @protocol PSPriorityNode<PSPrioritized>
    
    -(id)nodeKey;
    
    @end
    
    @protocol PSPrioritized<NSObject>
    
    -(NSNumber*)priority;
    
    @end
    
    

    Here is the Implementation of the Queue Entry object. This is very basic, we have a name that we can use to identify the object by – and for it to use as its hash value and to compare equality. We also have a priority value associated with it.

    
    @interface _PSTestPriorityQueueEntry : NSObject<PSPriorityNode>
    
    +(_PSTestPriorityQueueEntry*)peWithName:(NSString*)name
                                   priority:(NSInteger)priority;
    -(id)initWithName:(NSString*)name priority:(NSInteger)priority;
    
    @property(nonatomic, readonly, copy) NSString *name;
    
    -(NSNumber*)priority;
    -(id)nodeKey;
    
    @end
    
    
    @implementation _PSTestPriorityQueueEntry {
    	NSNumber *_priority;
    }
    
    +(_PSTestPriorityQueueEntry*)peWithName:(NSString*)name
                                   priority:(NSInteger)priority {
      return [[[_PSTestPriorityQueueEntry alloc] initWithName: name priority: priority] autorelease];
    }
    
    -(instancetype)initWithName:(NSString*)name priority:(NSInteger)priority {
      if(self = [super init]) {
        _name = [name copy];
        _priority = [@(priority) copy];
      }
    	
      return self;
    }
    
    -(void)dealloc {
      [_name release];
      [_priority release];
    
      [super dealloc];
    }
    
    -(NSNumber*)priority {
      return _priority;
    }
    
    -(id)nodeKey {
      return _name;
    }
    
    -(NSUInteger)hash {
      return [_name hash];
    }
    
    -(BOOL)isEqual:(id)object {
      if(self == object) {
        return YES;
      }
    	
      if(![object isMemberOfClass: [_PSTestPriorityQueueEntry class]]) {
        return NO;
      }
    	
      _PSTestPriorityQueueEntry *other = (_PSTestPriorityQueueEntry*)object;
    	
      return [self->_name isEqual: other->_name];
    }
    
    @end
    

    There are a few strategies that you can employ for your unit tests. I like to have some simple tests to ensure that all basic functionality is there. If a simple test fails, it’s probably also very simple to determine what went wrong and how to fix it.

    Once the simple tests are in place it’s time to consider the more complex interactions and the corner cases. You can’t cover everything, but the more you think through what possible corner cases there are, the better your code will be. The more complex scenarios and corner cases covered also means protection. If an enhancement to your code is added, you are certain to maintain the existing functionality if the unit test covers it.

    Below is the suite for the Priority Queue. We start off just by making sure it can be used as a basic heap sort. We move on to dequeueing the adding items, reprioritizing items, and reprioritizing if better (fail and succeed). For all the operations, I try to cover the Min Queue and Max Queue versions to make sure the code works for both scenarios.

    
    -(void)testSimpleSort {
      NSArray *list =
        @[ [_PSTestPriorityQueueEntry peWithName: @"dwarf" priority: 3],
           [_PSTestPriorityQueueEntry peWithName: @"axe" priority: 13],
           [_PSTestPriorityQueueEntry peWithName: @"sword" priority: 8],
           [_PSTestPriorityQueueEntry peWithName: @"kitten" priority: 1],
           [_PSTestPriorityQueueEntry peWithName: @"dolomite" priority: 5],
           [_PSTestPriorityQueueEntry peWithName: @"goat" priority: 4] ];
    	
      PSPriorityQueue *minQueue = [PSPriorityQueue minQueue];
      [list enumerateObjectsUsingBlock: ^(id<PSPriorityNode> entry, NSUInteger idx, BOOL *stop) {
        [minQueue enqueue: entry];
      }];
    	
    	
      XCTAssertEqualObjects([(_PSTestPriorityQueueEntry*)[minQueue dequeue] name],
                            @"kitten");
      XCTAssertEqualObjects([(_PSTestPriorityQueueEntry*)[minQueue dequeue] name],
                            @"dwarf");
      XCTAssertEqualObjects([(_PSTestPriorityQueueEntry*)[minQueue dequeue] name],
                            @"goat");
      XCTAssertEqualObjects([(_PSTestPriorityQueueEntry*)[minQueue dequeue] name],
                            @"dolomite");
      XCTAssertEqualObjects([(_PSTestPriorityQueueEntry*)[minQueue dequeue] name],
                            @"sword");
      XCTAssertEqualObjects([(_PSTestPriorityQueueEntry*)[minQueue dequeue] name],
                            @"axe");
      XCTAssertNil([minQueue dequeue]);
    	
      PSPriorityQueue *maxQueue = [PSPriorityQueue maxQueue];
      [list enumerateObjectsUsingBlock: ^(id<PSPriorityNode> entry, NSUInteger idx, BOOL *stop) {
        [maxQueue enqueue: entry];
      }];
    	
      XCTAssertEqualObjects([(_PSTestPriorityQueueEntry*)[maxQueue dequeue] name],
                            @"axe");
      XCTAssertEqualObjects([(_PSTestPriorityQueueEntry*)[maxQueue dequeue] name],
                            @"sword");
      XCTAssertEqualObjects([(_PSTestPriorityQueueEntry*)[maxQueue dequeue] name],
                            @"dolomite");
      XCTAssertEqualObjects([(_PSTestPriorityQueueEntry*)[maxQueue dequeue] name],
                            @"goat");
      XCTAssertEqualObjects([(_PSTestPriorityQueueEntry*)[maxQueue dequeue] name],
                            @"dwarf");
      XCTAssertEqualObjects([(_PSTestPriorityQueueEntry*)[maxQueue dequeue] name],
                            @"kitten");
      XCTAssertNil([maxQueue dequeue]);
    }
    
    -(void)testReprioritizeMin {
      NSArray *list =
        @[ [_PSTestPriorityQueueEntry peWithName: @"dwarf" priority: 3],
           [_PSTestPriorityQueueEntry peWithName: @"axe" priority: 13],
           [_PSTestPriorityQueueEntry peWithName: @"sword" priority: 8],
           [_PSTestPriorityQueueEntry peWithName: @"kitten" priority: 1],
           [_PSTestPriorityQueueEntry peWithName: @"dolomite" priority: 5],
           [_PSTestPriorityQueueEntry peWithName: @"goat" priority: 4] ];
    	
      PSPriorityQueue *minQueue = [PSPriorityQueue minQueue];
      [list enumerateObjectsUsingBlock: ^(id<PSPriorityNode> entry, NSUInteger idx, BOOL *stop) {
         [minQueue enqueue: entry];
      }];
    	
      _PSTestPriorityQueueEntry *reprioritizedDwarf =
        [_PSTestPriorityQueueEntry peWithName: @"dwarf" priority: 0];
      [minQueue reprioritize: reprioritizedDwarf];
    	
      XCTAssertEqualObjects([(_PSTestPriorityQueueEntry*)[minQueue dequeue] name], @"dwarf");
      XCTAssertEqualObjects([(_PSTestPriorityQueueEntry*)[minQueue dequeue] name], @"kitten");
    
      _PSTestPriorityQueueEntry *reprioritizedGoat =
        [_PSTestPriorityQueueEntry peWithName: @"goat" priority: 12];
      [minQueue reprioritize: reprioritizedGoat];
      _PSTestPriorityQueueEntry *reprioritizedSword =
        [_PSTestPriorityQueueEntry peWithName: @"sword" priority: 15];
      [minQueue reprioritize: reprioritizedSword];
      XCTAssertEqualObjects([(_PSTestPriorityQueueEntry*)[minQueue dequeue] name],
                            @"dolomite");
      XCTAssertEqualObjects([(_PSTestPriorityQueueEntry*)[minQueue dequeue] name],
                            @"goat");
      XCTAssertEqualObjects([(_PSTestPriorityQueueEntry*)[minQueue dequeue] name],
                            @"axe");
      XCTAssertEqualObjects([(_PSTestPriorityQueueEntry*)[minQueue dequeue] name],
                            @"sword");
      XCTAssertNil([minQueue dequeue]);
    }
    
    -(void)testReprioritizeMax {
      NSArray *list =
        @[ [_PSTestPriorityQueueEntry peWithName: @"dwarf" priority: 3],
           [_PSTestPriorityQueueEntry peWithName: @"axe" priority: 13],
           [_PSTestPriorityQueueEntry peWithName: @"sword" priority: 8],
           [_PSTestPriorityQueueEntry peWithName: @"kitten" priority: 1],
           [_PSTestPriorityQueueEntry peWithName: @"dolomite" priority: 5],
           [_PSTestPriorityQueueEntry peWithName: @"goat" priority: 4] ];
    
      PSPriorityQueue *maxQueue = [PSPriorityQueue maxQueue];
      [list enumerateObjectsUsingBlock: ^(id<PSPriorityNode> entry, NSUInteger idx, BOOL *stop) {
        [maxQueue enqueue: entry];
      }];
    
      _PSTestPriorityQueueEntry *reprioritizedDwarf =
        [_PSTestPriorityQueueEntry peWithName: @"dwarf" priority: 1000];
      [maxQueue reprioritize: reprioritizedDwarf];
    	
      XCTAssertEqualObjects([(_PSTestPriorityQueueEntry*)[maxQueue dequeue] name],
                            @"dwarf");
      XCTAssertEqualObjects([(_PSTestPriorityQueueEntry*)[maxQueue dequeue] name],
                            @"axe");
    	
      _PSTestPriorityQueueEntry *reprioritizedGoat =
        [_PSTestPriorityQueueEntry peWithName: @"goat" priority: 6];
      [maxQueue reprioritize: reprioritizedGoat];
      _PSTestPriorityQueueEntry *reprioritizedSword =
        [_PSTestPriorityQueueEntry peWithName: @"sword" priority: -4];
      [maxQueue reprioritize: reprioritizedSword];
      XCTAssertEqualObjects([(_PSTestPriorityQueueEntry*)[maxQueue dequeue] name],
                            @"goat");
      XCTAssertEqualObjects([(_PSTestPriorityQueueEntry*)[maxQueue dequeue] name],
                            @"dolomite");
      XCTAssertEqualObjects([(_PSTestPriorityQueueEntry*)[maxQueue dequeue] name],
                            @"kitten");
      XCTAssertEqualObjects([(_PSTestPriorityQueueEntry*)[maxQueue dequeue] name],
                            @"sword");
      XCTAssertNil([maxQueue dequeue]);
    }
    
    -(void)testReprioritizeIfBetterMin {
      NSArray *list =
        @[ [_PSTestPriorityQueueEntry peWithName: @"dwarf" priority: 3],
           [_PSTestPriorityQueueEntry peWithName: @"axe" priority: 13],
           [_PSTestPriorityQueueEntry peWithName: @"sword" priority: 8],
           [_PSTestPriorityQueueEntry peWithName: @"kitten" priority: 1],
           [_PSTestPriorityQueueEntry peWithName: @"dolomite" priority: 5],
           [_PSTestPriorityQueueEntry peWithName: @"goat" priority: 4] ];
    	
      PSPriorityQueue *minQueue = [PSPriorityQueue minQueue];
      [list enumerateObjectsUsingBlock: ^(id<PSPriorityNode> entry, NSUInteger idx, BOOL *stop) {
        [minQueue enqueue: entry];
      }];
    
      _PSTestPriorityQueueEntry *reprioritizedDwarf =
        [_PSTestPriorityQueueEntry peWithName: @"dwarf" priority: 0];
      [minQueue reprioritizeIfBetter: reprioritizedDwarf];  // better, will shift
    	
      XCTAssertEqualObjects([(_PSTestPriorityQueueEntry*)[minQueue dequeue] name],
                            @"dwarf");
      XCTAssertEqualObjects([(_PSTestPriorityQueueEntry*)[minQueue dequeue] name],
                            @"kitten");
    	
      _PSTestPriorityQueueEntry *reprioritizedGoat =
        [_PSTestPriorityQueueEntry peWithName: @"goat" priority: 12];
      [minQueue reprioritize: reprioritizedGoat];
      _PSTestPriorityQueueEntry *reprioritizedSword =
        [_PSTestPriorityQueueEntry peWithName: @"sword" priority: 15];
      [minQueue reprioritizeIfBetter: reprioritizedSword];	// Not better, won't shift
      XCTAssertEqualObjects([(_PSTestPriorityQueueEntry*)[minQueue dequeue] name],
                            @"dolomite");
      XCTAssertEqualObjects([(_PSTestPriorityQueueEntry*)[minQueue dequeue] name],
                            @"sword");
      XCTAssertEqualObjects([(_PSTestPriorityQueueEntry*)[minQueue dequeue] name],
                            @"goat");
      XCTAssertEqualObjects([(_PSTestPriorityQueueEntry*)[minQueue dequeue] name],
                            @"axe");
      XCTAssertNil([minQueue dequeue]);
    }
    
    -(void)testReprioritizeIfBetterMax {
      NSArray *list =
        @[ [_PSTestPriorityQueueEntry peWithName: @"dwarf" priority: 3],
           [_PSTestPriorityQueueEntry peWithName: @"axe" priority: 13],
           [_PSTestPriorityQueueEntry peWithName: @"sword" priority: 8],
           [_PSTestPriorityQueueEntry peWithName: @"kitten" priority: 1],
           [_PSTestPriorityQueueEntry peWithName: @"dolomite" priority: 5],
           [_PSTestPriorityQueueEntry peWithName: @"goat" priority: 4] ];
    	
      PSPriorityQueue *maxQueue = [PSPriorityQueue maxQueue];
      [list enumerateObjectsUsingBlock: ^(id<PSPriorityNode> entry, NSUInteger idx, BOOL *stop) {
        [maxQueue enqueue: entry];
      }];
    	
      _PSTestPriorityQueueEntry *reprioritizedDwarf =
        [_PSTestPriorityQueueEntry peWithName: @"dwarf" priority: 1000];
      [maxQueue reprioritizeIfBetter: reprioritizedDwarf];	// better, will shift
    	
      XCTAssertEqualObjects([(_PSTestPriorityQueueEntry*)[maxQueue dequeue] name],
                            @"dwarf");
      XCTAssertEqualObjects([(_PSTestPriorityQueueEntry*)[maxQueue dequeue] name],
                            @"axe");
    	
      _PSTestPriorityQueueEntry *reprioritizedGoat =
        [_PSTestPriorityQueueEntry peWithName: @"goat" priority: 6];
      [maxQueue reprioritize: reprioritizedGoat];
      _PSTestPriorityQueueEntry *reprioritizedSword =
        [_PSTestPriorityQueueEntry peWithName: @"sword" priority: -4];
      [maxQueue reprioritizeIfBetter: reprioritizedSword];	// Not better, won't shift
      XCTAssertEqualObjects([(_PSTestPriorityQueueEntry*)[maxQueue dequeue] name],
                            @"sword");
      XCTAssertEqualObjects([(_PSTestPriorityQueueEntry*)[maxQueue dequeue] name],
                            @"goat");
      XCTAssertEqualObjects([(_PSTestPriorityQueueEntry*)[maxQueue dequeue] name],
                            @"dolomite");
      XCTAssertEqualObjects([(_PSTestPriorityQueueEntry*)[maxQueue dequeue] name],
                            @"kitten");
      XCTAssertNil([maxQueue dequeue]);
    }
    
    

    Actual Priority Queue implementation coming next time!

    Implementing A* in Objective-C like you mean it

    Graph Theory is the study of structures that model pairwise relations between objects. It is applicable to many problems in Computer Science and aptitude in Graph Theory is positively correlated with passing those pesky tech interviews. One very common problem in the Graph Theory space is finding the shortest path between two vertices.

    A “Vertex” (sometimes node) is an abstraction of a point. An “Edge” connects two vertices. A “Path” between Vertices V1 and V2 is technically a sequence of edges that connect V1 and V2.

    (V1)---e1---(V2)------------e6--------------\
     \_____                         _____e5----(V5)
           \-e2---(V3)----e4---(V4)/
    

    In the above ASCII drawing a path between Vertices V1 and V2 is the sequence of edges { e1, e6 } – Let’s call this path P1. Another path is the sequence { e2, e4, e5 } – path P2. Which is shorter? Maybe P1? It consists of fewer edges right? Another detail about edges is that they can have weights associated with them. The path length will be the sum of the weights of the edges that comprise the path.

    So why talk about finding shortest paths? When you ask Siri to tell you how to get to the nearest Burger King, you bet there are some shortest paths being calculated. A very simplified view of how that might work is thinking of intersections as vertices and roads as edges. The algorithm might consider current traffic and road conditions to assign weights to the edges and try to discover the quickest way for you to get your McNuggets.

    Now think of almost any video game. Bad guys need to get from where they are to where you are if they want to kill you. They could just wander around randomly but that wouldn’t be very effective. Bad Guys in “Classic” games often knew their position relative to yours and would attempt to move towards you. An enterprising gamer would soon be able to trick them into getting stuck behind an object. The bad guy was too stupid to navigate to your position because it couldn’t calculate a proper path. 8-bits just weren’t enough.

    There are many algorithms to find shortest paths. Some are designed to find the shortest path between 2 Vertices. Some will find all shortest paths from one Vertex to all others. Some will even find the shortest paths from all to all in a graph.

    I would like to talk a little bit about one algorithm in particular today, A* (A Star). One way to increase efficiency in finding the shortest path is by not exploring edges that are unlikely to be part of the actual shortest path. A* works by using a heuristic to determine what vertex to process next. A* is very useful for grid based games because the heuristic is very easy to write.

    “But Kirk!” you exclaim, “How is a grid like a graph?”

    If you consider each square of the grid to be a Vertex, the edge is the infinitely small border between the square and its neighbor squares. This even allows representation of edge weights. In a game you might expect walking through mountains to be more expensive than walking on roads.

    I’m going to describe a very high level description of the algorithm. There are many places on the web to learn about most of the specifics, the purpose of this article is to elaborate on one important detail that most (even very well written articles) ignore.

    The algorithm traverses the graph beginning with the Start Point. Each Vertex it visits it adds to the Closed Set and checks to see if it has reached its destination. If it is at the destination it builds the path and returns. If not it explores all the neighboring Vertices that are not in the Closed Set and adds them to the Open Set. Then it selects the best option from the Open Set and repeats the visitation process.

    When the algorithm needs to choose the next node to visit, it consults the Open Set. A*’s advantage is that it chooses the node that is most likely based on the information that it currently has to be the next step on the shortest path. How does it do that? When the Vertex is added to the Open Set, the estimated weight of the final path that includes that Vertex is calculated by adding the current path weight with the value the heuristic returns for the remainder of the trip. When Vertices are being added to the Open Set, the Open Set might already contain that Vertex from a different origin. At this point it needs to be Reprioritized. Conceptually that’s a simple operation right? You search the Set to see if the Vertex is there. You check to see if this path is better, and you update the relevant values.

    “Ok, So are we done?”

    Nope. Pathfinding is an expensive operation, obviously accuracy is important, but if the calculations bring your game to a screeching halt, then we have a problem. Do we want less accurate faster pathfinding? Or can we get more performance out of the algorithm I described? Let’s try first to keep the accuracy and find the inefficiency.

    The Open Set I described has a few operations performed on it.

  • Insert Vertex
  • Remove “Best” Vertex
  • Update Vertex (Remove re-add?)
  •  
    So what happens if we use an NSMutableArray for those operations?

  • Insert is O(1), ok so far, so good.
  • Remove Best is a search O(n), and a remove O(n). Actually the search is an always search everything so best case is n operations to find the index to remove. Then the removal will copy the items in the array after the removal.
  • Updating the Vertex is a linear search, which means O(n). In our cases however, it is essentially free because we already located it.
  •  
    Can we use CFBinaryHeap?
    CFBinaryHeap is a bit unfriendly to use but we can wrap it if necessary to make it feel like a Cocoa object! Isn’t this a great idea? Let’s see:

  • Insert has an average case of O(1) and a worst case of O(log n).
  • Remove Best is O(log n) – that’s way better.
  • Update Vertex – Remove items until the item you want is located, modify it, then re-add the items. O(n)
  •  
    This solution seems a lot better than the NSMutableArray. The Remove Best Vertex operation is more common than the Update Vertex operation so there’s a win there. The Update Vertex is still a sore spot. Can we make it better?

    We’ll find out next time! In the meantime, here are the main parts of my A* implementation.

    -(NSArray*)pathFromNodeKey:(id)nodeKey {
      if(self.dataSource == nil) {
        return nil;
      }
    	
      PSPathNode *root = [_nodeClass nodeWithParent: nil
                                                key: nodeKey
                                               dest: _dest
                                             weight: 0];
      [_openSet enqueue: root];
      BOOL pathComplete = NO;
    
      NSMutableArray *finalPathTemp = nil;
      while(!pathComplete) {
        PSPathNode *bestNode = (PSPathNode*)[_openSet dequeue];
        [_closedSet addObject: bestNode];
    
        if([[bestNode nodeKey] isEqual: _dest]) {
          // FOUND THE DESTINATION!
          finalPathTemp = [NSMutableArray array];
          PSPathNode *current = bestNode;
          while(current != nil) {
            [finalPathTemp addObject: current];
            current = [current parent];
          }
          pathComplete = YES;
        } else {
          // Process surrounding points
          for(id neighbor in [_dataSource neighborsOf: bestNode]) {
            [self processNode: neighbor parent: bestNode];
          }
        }
        if([_openSet count] == 0) {
          break;
        }
        [self stateDump];
      }
    
      return finalPathTemp == nil ? nil : [[finalPathTemp reverseObjectEnumerator] allObjects];
    }
    
    -(void)processNode:(id)nodeKey parent:(PSPathNode*)parent {
      if([_closedSet containsObject: nodeKey]) {
        // If we're in the closed set bounce
        return;
      }
    
      NSInteger cost = [_dataSource costFrom: [parent nodeKey] to: nodeKey];
      if(cost <= 0) {
        // If we can't pass that square bounce
        return;
      }
    
      PSPathNode *newNode = [_nodeClass nodeWithParent: parent
                                                   key: nodeKey
                                                  dest: _dest
                                                weight: cost];
      if(![_openSet contains: newNode]) {
        // If not in the open set, add to it
        [_openSet enqueue: newNode];
      } else {
        // In the open set but let's see if this is a better way
        [_openSet reprioritizeIfBetter: newNode];
      }
    }
    

    7drl 2014

    I’m currently on day 5 of the 7drl 2014 contest. EmojiRogue is a roguelike playable through Twitter. I’m not sure if it’s the first of its kind, but I’ve never seen one. I wish I had more time to work on it, but unfortunately that’s not the case.

    Design was an interesting exercise – first, given that we’re dealing with passing messages back and forth so a) getting as much done as possible with each message, and b) making so the game itself lacks the complexities that require lots of interaction. Given that we have Emoji “Tiles” – the design is dictated by what was available. Surprisingly many things are covered! The one that amused me the most was my decision to use the syringe as the “magic potion”.

    Unfortunately for non-apple users EmojiRogue might look bad or some symbols might be unrecognizable. There isn’t much I can do for Windows/Linux/Android, Apple just provides a really awesome Emoji set and their competitors don’t.

    Time is running out and there isn’t much “game” yet. Even if I don’t succeed in something playable by Friday night, this project was a huge success for me. I wrote a server on the Mac using GCD. I learned parts of the Twitter API (and was greatly frustrated by the OAuth aspect). I also got to apply the Philosopher’s Stone library, which is a key component to The Lonely Dwarves (see my previous developer’s journals) to an OS X project. This gives me access to a bunch of useful code that I have already tested including my recursive shadowcaster and pathing code.

    One aspect of Twitter that almost made me give up is the fact that they toss out “duplicate” tweets. That’s fine if you’re trying to spam “LOL I POOPED #YOLO” over and over again, but it prevents giving a command for the second time. Let’s say you wanted your character status. The command for that would look something like “@emojirogue status”. Getting to use that command once is a deal breaker. My best workaround is having the user put a number in front of each command (any garbage will do, so long as it’s unique garbage), but I can return the next number in each reply. So you might ask status like, “@emojirogue 14 status” and later as “@emojirogue 43 status”. It’s not perfect, but this is really just an experiment right?