Game Development – part 1

Starting on my own game, although brilliant idea is immensely dependent on how the stars are aligned (metaphorical speaking obviously) still I can’t disclose the exact concept since the indie game scenery is notoriously brutal, but in a glimpse the basic premise is a maze with a few added twists.
じゃあ、いきましょうー!

Choosing the Framework

There were candidates, which were

  1. oF, because of Ridiculous Fishing.
  2. cocos2D, because of Badland
  3. Native, because of iOS7
  4. and lastly cocos2d-x, because its porting capabilities

At the end I have chosen cocos2d-x because mobile != iOS, although hindsight native was perhaps a better choice since cocos2d-x is inferior in comparison with iOS 7, its laden with flaws such as the documentation, slow update, and mainly performance, on dormant the CPU usage hovers around 16%

Screenshot
as native, it can go as low as 5%.

Although this is just my opinion, a diehard cocos2d-x user might argue au contraire.

Development

First phase is building the maze-generator, there a lot of maze algorithm out there and some uses fancy algorithm such as Gabriel Graph, Relative neighborhood graph, or Normal distribution but I chose Depth-first search since the game has to be simple and fast.

/**

Build an empty maze

*/
void MazeGenerator::addInit() {
    
    int i;
    
    for (i = 0; i < _total; i++) {
        
        // _w is width of the tiles
        int flag = EMPTY, nh = i/_w;
        
        if (i < _w || i > _total-_w-1 || i%_w == 0 || i%(_w*(nh+1)-1) == 0 || (i%2 != 0 && nh%2 != 0)) {
            flag = WALL;
        }
        
        if (_start < 0 && flag == EMPTY) {
            _start = i;
            
            // TODO randomize start position
            flag = START;
        }
        
        if (flag != EMPTY) _empty--;
        
        _stage->addObject(CCInteger::create(flag));
        
    }
}

/**

Add the Depth-first search

*/
void MazeGenerator::addDepthSearch() {
    
    CCArray* stack = CCArray::create();
    CCInteger* p;
    CCInteger* q;
    
    int s = _start;
    
    while (_path < _empty) {
        
        // Check for any surrounding empty tiles
        CCArray* r = checkSurrounding(_stage, s, EMPTY);
        
        // If exists
        if (r->count() > 0) {
            
            p = dynamic_cast<CCInteger *>(r->objectAtIndex(rand()%r->count()));
            
            _stage->replaceObjectAtIndex(p->getValue(), CCInteger::create( PATH ));
            s = p->getValue();
            
            // TODO randomize end position
            if (_end < s) _end = s;
            
            stack->addObject(p);
            
            _deadend = 1;
            
            _path++;
            
        } else {
            
            // Add a cul-de-sac
            if (_deadend > 0) {
                
                q = dynamic_cast<CCInteger *>( stack->lastObject());
                
                _stage->replaceObjectAtIndex(q->getValue(), CCInteger::create( WALL ));
                
                _deadend = -1;
            }
            
            // if cul-de-sac reached, step back 
            stack->removeLastObject();
            p = dynamic_cast<CCInteger *>( stack->lastObject());
            
            s = p->getValue();
        }
        
    }
    
}

And here’s the result


// 11x11 tiles
// 7 = Starting point
// 8 = Ending point
// 0 = Wall
// 6 = Path

0,0,0,0,0,0,0,0,0,0,0,
0,7,0,0,0,0,0,0,0,0,0,
0,6,0,6,6,6,6,6,6,6,0,
0,6,0,0,0,0,0,0,0,6,0,
0,6,6,6,0,6,6,6,6,6,0,
0,0,0,6,0,6,0,0,0,6,0,
0,6,0,6,0,6,0,6,0,6,0,
0,6,0,6,0,6,0,6,0,6,0,
0,6,6,6,6,6,0,6,6,6,0,
0,0,0,6,0,0,0,0,0,8,0,
0,0,0,0,0,0,0,0,0,0,0,

And another thing is path finding, the first choice is of course A*, but I removed/modified several things;

  1. The past path-cost function, as is not required
  2. The open and close list, since I thought duplicating the scene array and tagging it with a different number would be faster, there’s no need for additional iterations nor added processing to deconstruct the extra arrays.
  3. And as for the future path-cost function I employed the Manhattan Method, which goes something like this.
H = 10*(abs(currentX-targetX) + abs(currentY-targetY))[/cc]

Simple enough, note the coefficient 10 is not necessary unless you're dealing with decimal, I used it just for the sake of it 凸(`0´)凸


void MazeGenerator::addPathfinding() {
    
    // Duplicate the stage
    _pfind = CCArray::create();
    _pfind->addObjectsFromArray(_stage);
    
    CCArray* stack = CCArray::create();
    CCArray* r;
    CCInteger* p;
    
    int s = _start, pos = 0;
    
    while (_path > 0) {
        
        // Check surrounding for Path
        r = checkSurrounding(_pfind, s, PATH);
        
        // If path exists
        if (r->count() > 0) {
            
            int temp = 0;
            
            for (int i = 0; i < r->count(); i++) {
                
                p = dynamic_cast<CCInteger *>(r->objectAtIndex(i));
                
                temp = getCost(p->getValue());
                
                // to filter smallest cost
                if(temp < pos) pos = temp;
                
            }
            
            // Mark the path with 1
            _pfind->replaceObjectAtIndex(pos, CCInteger::create( 1 ));
            stack->addObject(CCInteger::create( pos ));
            
            // break if end reached
            CC_BREAK_IF(_end == pos);
            
            _path--;
            
        } else {
            
            if cul-de-sac, step back
            stack->removeLastObject();
            p = dynamic_cast<CCInteger *>( stack->lastObject());
            
            s = p->getValue();
        }
 
    }
    
}

/**

The Manhattan Method

*/
int MazeGenerator::getCost(int p) {
    
    int x0 = _end%_w,
        y0 = _end/_w,
        x1 = p%_w,
        y1 = p/_w;
    
    return 10*(abs(x1-x0)+abs(y1-y0));
    
}

And the results is pretty good.


// 1 = Routes

0,0,0,0,0,0,0,0,0,0,0,
0,7,0,0,0,0,0,0,0,0,0,
0,1,0,6,6,6,6,6,6,6,0,
0,1,0,0,0,0,0,0,0,6,0,
0,1,1,1,0,1,1,1,1,1,0,
0,0,0,1,0,1,0,0,0,1,0,
0,6,0,1,0,1,0,6,0,1,0,
0,6,0,1,0,1,0,6,0,1,0,
0,6,6,1,1,1,0,6,6,1,0,
0,0,0,1,0,0,0,0,0,1,0,
0,0,0,0,0,0,0,0,0,0,0,

Until next time.

Leave a Reply

Your email address will not be published. Required fields are marked *