AI and path finding challenges

[M_D_K]

This is a "testing the water" type deal. I have a few challenge ideas relating to well see title.
And no point in posting them if no one will do them(or even try) so quick show of hands who would be interested.

[MarauderIIC]

interested dunno if i'll do them

[Spikey]

I actually have an assignment thats due next week about the A* algorithm. I've never done this before, so I'm up for the challange...

[avansc]

So when is this coming?

(thats what she said.)

[dandymcgee]

Personally I'm not a very competitive programmer, but I'm very interested to see solutions to common AI problems.

[eatcomics]

I do loves me the AI and UI elements of a game

[Spikey]

Working on my homework, actually due later today...
Turns out I wasn't supposed to use A* algorithm, but rather a linked list routine.

In my project, I have a class called MazeNode, which represents 1 spot on a map/maze. My nodes have pointers to 4 other nodes, 1 for each direction (North, East, etc). Each node can point from 1 to 4 more nodes, which those can also point to more.

Once a map/maze is constructed, we start at the first node aka Start node. From here we check each direction to see if there is node linked, if there is a node in a direction, we check to see if we have visited there, if not then go to that node. If node has visited all of its directions or has no nodes to advance to, then we go back to previous node. Keep this up until we find our goal node aka End node.

Did I make no sense? Check out the readme.txt and source to see step by step comments and notes:
http://subversion.assembla.com/svn/schi0102/
Goto trunk for latest source, goto branch for binary ( .exe )

Right now, (Apr 9, `09 - 4AM) Everything works except for RandomMaze.h, I still need to make a routine to generate a random maze... But pathfinding code is all good as far as I can see.

...I can has cheezburger?

[kostiak2]

Nice design, Spikey, but do you realy stop once you reach the goal for the first time? cause that will find a path to the distanation, but that path could be going around the entire map.

for example you want to go from A to B on that map

*****************
*****************
***A************
***B*************
*****************

your salution (if i understand it correctly) may come back with the following path:

v<<<<<<<<<<<
>>>>>>>>>>v^
***A<<<<<<<<^
***B>>>>>>>>^
*****************

Or am i missing something?

[Spikey]

Your right, this version does not stop when it finds the goal. Thats a easy fix, from the solvemaze function, 'return' after finding the goal. It was intentionally left off, because I wanted to see what would happen if the path never found a goal. It could also be useful for finding multiple goals or future optimization for shortest route.
I don't think the path will ever loop, each passed node is pushed onto a stack and each node is marked whether the path has been there already or not.
I'm not sure what you're trying to say with your diagrams... If you havent already, check out the exe, solving the test map with details showing, this will output every push, pop, check, detail, etc while solving. Hopefully that helps.

[MarauderIIC]

A* should always return most efficient path, iirc, as long as your heuristics are right.

[kostiak2]

that's what i was saying:


Instead of going strait up, which is what A* should return if i remember correctly.

[Spikey]

Ok, understood. Ya I wasn't really going for effeciency here, just glad I was able to get from point a to b. This assignment is done, I've handed it in as is, I was working on a random map generator and it seems to work most of the time....

[wearymemory]

that's what i was saying:


Instead of going strait up, which is what A* should return if i remember correctly.

Not always, according to the article that lies behind this magical text. It also states what constitutes a path finding method as A*, not that you asked.

Since the assignment is finished and already handed in, this is my solution (Not that many of you care, I'm sure):

Click here to see the hidden message (It might contain spoilers)

Code: Select all

#include <iostream>
#include <vector>


using namespace std;

 char maze[10][10] = {
        {'X', 'X', 'S', 'X', 'X', 'X', 'X', 'X', 'X', 'X'},
        {'X', 'X', 'O', 'X', 'X', 'X', 'X', 'X', 'X', 'X'},
        {'X', 'X', 'O', 'O', 'O', 'O', 'O', 'X', 'X', 'X'},
        {'X', 'X', 'O', 'X', 'X', 'X', 'X', 'O', 'O', 'X'},
        {'X', 'X', 'O', 'O', 'O', 'O', 'X', 'X', 'X', 'X'},
        {'X', 'X', 'X', 'X', 'X', 'O', 'X', 'X', 'X', 'X'},
        {'X', 'X', 'X', 'X', 'X', 'O', 'X', 'X', 'X', 'X'},
        {'X', 'X', 'X', 'O', 'O', 'O', 'O', 'O', 'X', 'X'},
        {'X', 'X', 'X', 'O', 'X', 'X', 'X', 'O', 'X', 'X'},
        {'X', 'X', 'X', 'X', 'X', 'X', 'X', 'E', 'X', 'X'}};

template <typename T, size_t N>
char (&array(T(&)[N]))[N];

struct Point {
    int x;
    int y;

    Point(int x, int y) : x(x), y(y) {}
};

bool contains(vector<Point> v, Point point) {
    for(int i = 0; i < v.size(); i++) {
        if(v[i].x == point.x && v[i].y == point.y) {
            return true;
        }
    }
    return false;
}


bool step(Point start, Point finish, vector<Point> v) {
    if(start.x < 0 || start.x >= sizeof array(maze[0]) 
    || start.y < 0 || start.y >= sizeof array(maze) 
    || maze[start.y][start.x] == 'X') {
        return false;
    }

    v.push_back(start);

    if(start.x == finish.x && start.y == finish.y) {
        cout << "Path:";
        for(int i = 0; i < v.size(); i++) {
            cout << " (" <<  v[i].x << ", " << v[i].y << ")";
        }
        cout << endl;
        return true;
    }

    Point up(start.x, start.y-1);
    Point down(start.x, start.y+1);
    Point left(start.x-1, start.y);
    Point right(start.x+1, start.y);

    bool b;

    if(!contains(v, up)) b = step(up, finish, v);
    if(!contains(v, down)) b |= step(down, finish, v);
    if(!contains(v, left)) b |= step(left, finish, v);
    if(!contains(v, right)) b |= step(right, finish, v);

    return b;
}

int main() {
    step(Point(2, 0), Point(7, 9), vector<Point>());
    return 0;
}

[M_D_K]

lolz no official challenges have been posted by me. This thread was just to see if people would be interested. Thats why there is a poll.

BTW who the fuck said voted "WTF is AI"

[MarauderIIC]

Oh, there's a poll.