iPhone迷路の最短

タッチで自作する迷路の最短経路を表示する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