タッチで自作する迷路の最短経路を表示するiPhoneアプリのサンプルコードを描いてみます。
#import “ViewController.h”
// manualy added – link binary with libraries –
#import <SpriteKit/SpriteKit.h>
#include <memory>
#include <queue>
using namespace std;
#define MAX_X 8
#define MAX_Y 8
#define TILE 1
#define WALL 2
#define INF 1000000
typedef pair<int, int> P;
class ShortestPathResolver {
public:
void solve(int[][MAX_Y], CGPoint, CGPoint);
int d[MAX_X][MAX_Y];
private:
int maze[MAX_X][MAX_Y];
int sx, sy, gx, gy;
int bfs();
};
void ShortestPathResolver::solve(int m[][MAX_Y], CGPoint start, CGPoint goal) {
for (int i=0; i<MAX_X; i++)
for (int j=0; j<MAX_Y; j++) maze[i][j] = m[i][j];
sx = start.x, sy = start.y;
gx = goal.x, gy = goal.y;
bfs();
}
int ShortestPathResolver::bfs() {
queue<P> queue;
for (int i=0; i< MAX_X; i++)
for (int j=0; j < MAX_Y; j++) d[i][j] = INF;
queue.push(P(sx, sy));
d[sx][sy] = 0;
int dx[] = {1, 0, –1, 0}, dy[] = {0, 1, 0, –1};
while (queue.size()) {
P p = queue.front(); queue.pop();
if (p.first == gx && p.second == gy) {
break;
}
for (int i=0; i<4; i++) {
int nx = p.first + dx[i], ny = p.second + dy[i];
if (0 <= nx && nx < MAX_X && 0 <=ny && ny < MAX_Y && maze[nx][ny] != WALL && d[nx][ny] == INF) {
// can move
queue.push(P(nx, ny));
d[nx][ny] = d[p.first][p.second] + 1;
}
}
}
return d[gx][gy];
}
@interface ViewController ()
@property (nonatomic, weak) SKScene *scene;
@property (nonatomic, strong) NSMutableArray *mazeArr;
@end
@implementation ViewController
– (void)viewDidLoad {
[super viewDidLoad];
[self createMap];
}
– (void)createMap {
// setup scene
SKView *sv = [[SKView alloc] initWithFrame:self.view.bounds];
SKScene *s = [SKScene sceneWithSize:sv.frame.size];
s.backgroundColor = [UIColor colorWithHue:0.7 saturation:0.2 brightness:1 alpha:1];
[sv presentScene:s];
[self.view addSubview:sv];
self.scene = s;
// map
self.mazeArr = [NSMutableArray array];
for (int i=0; i<64; i++) {
float x = (i % 8) * 40 + 50;
float y = (i / 8) * 40 + 250;
SKSpriteNode *tile = [SKSpriteNode spriteNodeWithColor:[UIColor whiteColor] size:CGSizeMake(38, 38)];
tile.position = CGPointMake(x, y);
[self.scene addChild:tile];
if (i==2) { // start point
tile.color = [UIColor blueColor];
tile.name = @”start”;
SKLabelNode *l = [SKLabelNode labelNodeWithText:@”S”];
l.name = @”start”;
l.position = CGPointMake(0, –15);
[tile addChild:l];
} else if (i == 62) { // goal
tile.color = [UIColor redColor];
SKLabelNode *l = [SKLabelNode labelNodeWithText:@”G”];
l.position = CGPointMake(0, –15);
[tile addChild:l];
} else { // other
tile.name = @”tile”;
}
[self.mazeArr addObject:tile];
}
}
– (void)touchesBegan:(NSSet *)touches withEvent:(UIEvent *)event {
CGPoint p = [[touches anyObject] locationInNode:self.scene];
SKNode *n = [self.scene nodeAtPoint:p];
if ([n.name isEqual:@”start”]) {
shared_ptr<ShortestPathResolver> cppClass(new ShortestPathResolver());
int maze[MAX_X][MAX_Y];
for (int i=0; i<self.mazeArr.count; i++) {
int x = (i % 8);
int y = (i / 8);
SKNode *n = self.mazeArr[i];
if ([n.name isEqual:@”tile”]) {
maze[x][y] = TILE;
}
else if ([n.name isEqual:@”wall”]) {
maze[x][y] = WALL;
} else {
maze[x][y] = 0;
}
}
cppClass->solve(maze, CGPointMake(2, 0), CGPointMake(6 ,7));
for (int i=0; i<MAX_X; i++) {
for (int j=0; j<MAX_X; j++) {
NSString *str = cppClass->d[i][j] < 100 ? [NSString stringWithFormat:@”%d”, cppClass->d[i][j]] : @”N”;
SKLabelNode *l = [SKLabelNode labelNodeWithText:str];
l.fontSize = 12;
l.fontName = [UIFont boldSystemFontOfSize:10].fontName;
l.fontColor = [UIColor darkGrayColor];
[self.mazeArr[i + j * 8] addChild:l];
}
}
} else if ([n.name isEqual:@”tile”]) {
[n runAction:[SKAction fadeOutWithDuration:0.3] completion:^{
((SKSpriteNode *) n).color = [UIColor brownColor];
[n runAction:[SKAction fadeInWithDuration:0.4]];
}];
n.name = @”wall”;
} else if ([n.name isEqual:@”wall”]) {
((SKSpriteNode *) n).color = [UIColor whiteColor];
n.name = @”tile”;
}
}
@end