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
- oF, because of Ridiculous Fishing.
- cocos2D, because of Badland
- Native, because of iOS7
- 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%
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;
- The past path-cost function, as is not required
- 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.
- 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.
