Quantcast

Maximum PC

It is currently Wed Oct 22, 2014 2:53 pm

All times are UTC - 8 hours




Post new topic Reply to topic  [ 33 posts ]  Go to page 1, 2  Next
Author Message
 Post subject: (Discussion) Pathfinding
PostPosted: Mon Oct 04, 2010 1:46 pm 
Northwood
Northwood
User avatar

Joined: Sun Jul 15, 2007 6:37 pm
Posts: 2261
Location: No. 1 Thread Killer
This is meant for discussion and getting better. If you guys solve the problem i'll give tougher questions :D.

It's something that's been on my mind lately.... but let's say you have a two dimensional array and need to get from the left to right of the array.... the array is of x >= 4 and y >= 4 size, but no matter what, there IS a way to get from the left to the right side.

so the rules:
The "player" always starts from [0][0].
Can't move diagonally
The traversable path is made up of 0's and the path you cannot pass is made up of 1's
Array is x >= 4 and y >= 4 size.
There is, no matter what, a way from one end to another.
Once you hit the right side of the 'map' you "win"

in perl such an array would look like this:
@matrix = (
[0, 1, 1, 0, 0],
[0, 0, 1, 1, 0],
[1, 0, 1, 0, 0],
[1, 0, 0, 0, 1]
);

Think you can demonstrate that your program made it through by replacing the 0's?

If you solve that with ease, what about making such arrays procedurally?

My posting is finicky so i'm going to hold on my answer(s) for now.

I know you guys can solve this problem with ease, and if you do, complicate it a bit, i have something else that's tougher but i'm going to have to finish my path-generation procedurally thing first.


Top
  Profile  
 
 Post subject: Re: (Discussion) Pathfinding
PostPosted: Mon Oct 04, 2010 2:09 pm 
Java Junkie
Java Junkie
User avatar

Joined: Mon Jun 14, 2004 10:23 am
Posts: 24226
Location: Granite Heaven
This is a good question to help people thinking about tree traversals.

Consider (0,0) to be the root of the tree. From there, you can go right (0,1) or down (1,0). Each direction of travel is a branch of the tree.

Finding the 'right side' becomes a question of 'searching' for the closest node on the right side. A DFS would turn it up pretty quickly.


Top
  Profile  
 
 Post subject: Re: (Discussion) Pathfinding
PostPosted: Mon Oct 04, 2010 4:00 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
Dwood15 wrote:
Think you can demonstrate that your program made it through by replacing the 0's?

Yes. Either DFS or BFS solves this problem quite easily. If you wanted to get fancy, you could even use something like bi-directional search which could prove effective on this type of graph.

I can't think of any spectral techniques off-hand, but I wouldn't be surprised to hear that some exist either.

Dwood15 wrote:
If you solve that with ease, what about making such arrays procedurally?

There are quite a few methods you could employ to create a graph with a valid path. Try performing a random walk from one or more accepting nodes to the start node.


Top
  Profile  
 
 Post subject: Re: (Discussion) Pathfinding
PostPosted: Mon Oct 04, 2010 4:03 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
Jipstyle wrote:
This is a good question to help people thinking about tree traversals.

Jipstyle makes an interesting point. Clearly, the array represents a graph. (Why?)

So can it be solved using a "tree traversal"? (Why?)


Top
  Profile  
 
 Post subject: Re: (Discussion) Pathfinding
PostPosted: Sat Oct 09, 2010 2:04 am 
Team Member Top 100
Team Member Top 100

Joined: Sun Feb 12, 2006 2:52 pm
Posts: 1994
Location: Cryptogram City!
Sounds like Hill Climbing to me! 8)

This was coded in Turbo C, but it can easily be altered. Shows visual hill climbing in an array, with step constraints of one value, maximum.

Code:
/* an example of basic Hill Climbing, constrained by a step maximum
Adak, June 16, 2010
status: OK
*/

#include <stdio.h>
#include <conio.h>
#include <dos.h>

#define ROWS 8

struct point {
  int row;
  int col;
  int value;
}p1;

void info(void);

int main() {
  int i, j, step, max, last_value, new_value;
  int x, y, x1, y1;
  int hill[ROWS][ROWS] = {      //correct local maxima is at hill[0][7]
  { 0,  1,  0,  0,  0,  0,  0, 17 },
  { 3,  1,  2,  0,  0,  0, 16,  0 },
  { 3,  3,  0,  8, 20, 15,  0,  0 },
  { 0,  4,  5,  9,  0,  8, 14,  0 },
  { 0,  0,  6,  7,  9, 13,  8,  0 },
  { 0,  0,  8,  0, 12,  8,  8,  0 },
  { 0,  9,  8, 11,  0,  0,  0,  0 },
  { 0,  0, 10,  0,  0,  0,  0,  0 }
  };
  struct point p2;
  step=1;
  printf("\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n");
  info();
  p2 = p1;
  gotoxy(1,5);
  textcolor(14);  //affects only cprintf() "direct video" output
  printf("\n    0   1   2   3   4   5   6   7");
  printf("\n    =============================\n");

  for(i=0;i<ROWS;i++) {
    printf("%d: ", i);
    for(j=0;j<ROWS;j++) {
      if(i==0 && j==0) {
        printf("%2d",hill[i][j]);
        cprintf("* ");
      }
      else
        printf("%2d  ",hill[i][j]);
    }
    putchar('\n');
  }
  printf("\n From row 0, column 0, climb to:");
  do {
    p1.value = hill[p1.row][p1.col];
    last_value = p1.value;
    max = p1.value + step;
    for(i=0; i<8; i++) {
      if(i==0 && p1.row > 0) {                    //12 o'clock
        p2.row = p1.row -1;
      }
      else if(i==1 && p1.row > 0) {               //1:30 o'clock
        p2.row = p1.row -1;
        p2.col = p1.col +1; 
      }
      else if(i==2 && p1.col < ROWS -1)           //3 o'clock
        p2.col = p1.col +1;
      else if(i==3 && p1.row < ROWS -1 && p1.col < ROWS -1) { //4:30 o'clock
        p2.row = p1.row +1;
        p2.col = p1.col +1;
      }
      else if(i==4 && p1.row < ROWS -1)           //6 o'clock
        p2.row = p1.row +1;
      else if(i==5 && p1.row < ROWS -1 && p1.col > 0) {  //7:30 o'clock
        p2.row = p1.row +1;
        p2.col = p1.col -1;
      }
      else if(i==6 && p1.col > 0)                  //9 o'clock
        p2.col = p1.col -1;
      else if(i==7 && p1.row > 0 && p1.col > 0) {  //10:30 o'clock
        p2.row = p1.row -1;
        p2.col = p1.col -1;
      }
      p2.value = hill[p2.row][p2.col];
      if(p2.value > p1.value && p2.value <= max) {
        p1 = p2;
        break;
      }   
      else
        p2 = p1;
    }
    new_value = p1.value;
    if(new_value > last_value) {
      x1 = wherex();
      y1 = wherey();
      x=6+(p1.col*4);
      y=8+p1.row;
      gotoxy(x,y);
      cprintf("*");
      gotoxy(x1,y1);
      if(new_value % 2)
        putchar('\n');
      printf("  >> row: %d, col: %d, value: %2d", p1.row,p1.col,p1.value);
    }
    sleep(1); //pause for 1 second
  }while(new_value > last_value);
  printf("\n\n\t\t\t     press enter when ready");

  (void) getchar();
  return 0;
}
void info(void) {
  int i;
  printf("  An example of Hill Climbing, in an array. From the start at\n");
  printf("  the top left row and column, each step must be:\n\n");
  printf("    * to a higher value, and \n    * no more than the current value + 1\n");
  printf("\n  This algorithm finds the local maximal value, which may or may not\n\
  be the greatest value in the array.");
  printf("  Here, it misses the highest\n  value of 20, near the center of the array.\n");
  printf("\n\n\n\n\n\n\n\n\n\n\n\t\t\t     press enter when ready\n");
  (void) getchar();
  for(i=0;i<4;i++)
    printf("\n\n\n\n\n\n\n\n\n\n\n\n");
}


The executable (runs in Windows XP, at least), can be d/l'd from:
http://en.swoopshare.com/file/0088f549c ... MB&lang=en


Top
  Profile  
 
 Post subject: Re: (Discussion) Pathfinding
PostPosted: Wed Oct 13, 2010 1:54 pm 
Northwood
Northwood
User avatar

Joined: Sun Jul 15, 2007 6:37 pm
Posts: 2261
Location: No. 1 Thread Killer
Thanks, Adak! That was something I was considering when I was writing my arrays as well! :P

Sadly, I don't have my solution to the two proposed problems but it's fairly simple, first checking all of the surrounding 0's first, then following that zero if it wasn't the one previous. if it hits ones on all 3 sides it traces itself back till it hits another branch (not one it hasn't traversed before) that hasn't been explored. rinse, repeat.


Top
  Profile  
 
 Post subject: Re: (Discussion) Pathfinding
PostPosted: Wed Oct 13, 2010 11:59 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
Adak wrote:
Sounds like Hill Climbing to me! 8)


As if the biz app/web programmers around here weren't bad enough... now we have a non-cs programmers suggesting search algorithms! =)

For the benefit of those who may not be aware of it, hill climbing is generally employed when dealing with large search spaces (ie where large is something non-trivial like possible chess moves to a certain depth) when you're not likely to find the optimal answer. Even then, it is actually not considered to be all that good of a solution compared to other methods. For example, theorists would probably pull out one or more approximation algorithms or linear programming then follow up with a branch/bound search or a better local search algorithm. The AI folks might pull out hill climbing, but they're just as likely to pull out something better suited for a given problem as well (eg a heuristic search algorithm, CSP, etc depending on the problem). Hill climbing tends to be used when you can't think of anything better than a naive solution (ie brute-force solution) and a brute-force algorithm won't work because of the large search space.

For this problem, DFS or BFS will provide an optimal answer to any problem instance that Dwood15 could send your way. How do I know this? Well, every problem has (at least) three time-complexity components:

1. The amount of time it takes to verify an answer
2. The amount of time it takes to find a solution to a problem.
3. The amount of time it takes to create an instance of a problem.

Using DFS, the worst-case time complexity is the maximum of the number of vertices or number of edges in the graph (ie O(|v| + |e|). In a large graph, most of the nodes will contribute two additional edges, therefore |e|=O(2v). Now the important thing to consider is how long does it take to generate a valid problem instance? Let's assume that dwood15 comes up with a kick-arse algorithm that creates the graph in O(|e|^2) time then dedicates an entire year of computing time creating a giant 1024 edge graph (obviously, it would be larger, but lets keep the math simple).

How long does it take you to solve it? Think about it before going on... =)

Restating the problem, if 1024^2 represents one year of computing time, then how long does it take us to solve the problem using an O(|e|) algorithm? Obviously, we're able to solve the problem in 1024 ie 2^10. Since 1024^2 = 2^20 represents a year, it takes us is 2^10 / 2^20 time which reduces to 1 / 2^10 which comes to about 8 hours of computing time. DFS FTW!


Top
  Profile  
 
 Post subject: Re: (Discussion) Pathfinding
PostPosted: Thu Oct 14, 2010 12:02 am 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
Dwood15 wrote:
Sadly, I don't have my solution to the two proposed problems but it's fairly simple, first checking all of the surrounding 0's first, then following that zero if it wasn't the one previous. if it hits ones on all 3 sides it traces itself back till it hits another branch (not one it hasn't traversed before) that hasn't been explored. rinse, repeat.

This sounds familiar... =)

Checking that 0 if it wasn't the one previous? How about if it hasn't been expanded regardless of whether it was the previous node instead?


Top
  Profile  
 
 Post subject: Re: (Discussion) Pathfinding
PostPosted: Fri Oct 15, 2010 7:54 am 
SON OF A GUN
SON OF A GUN
User avatar

Joined: Mon Nov 01, 2004 5:41 am
Posts: 11605
A*

/thread


Top
  Profile  
 
 Post subject: Re: (Discussion) Pathfinding
PostPosted: Sat Oct 16, 2010 5:20 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
CrashTECH wrote:
A*

/thread

Hardly. For starters, how are you going to handle multiple goal nodes? You could always run the search multiple times (start, end1), (s,e2), (s,en), but this doesn't strike me as being very efficient. Is there a better solution?

Have you written the heuristic function? After all, this isn't the road network example from Russell and Norvig -- it is a maze! And are you calculating the Euclidean distance from your current location to a nearest goal, while using the Manhattan distance for the portion that you've already covered? And you do realize that we're dealing with an entirely different metric space now, one in which several paths will have the same distance: http://en.wikipedia.org/wiki/File:Manha ... stance.svg

I'd would love to see an A* solution, but my hunch is that it wouldn't do much better than DFS. Here is another consideration: the distance between every node is 1. While your solution is adding 1's on top of 1's, and vainly trying to find a shortcut through the maze (and probably getting just as lost as ours), our solutions are blindly making progress, blindingly fast progress, towards a solution.


Top
  Profile  
 
 Post subject: Re: (Discussion) Pathfinding
PostPosted: Tue Oct 19, 2010 4:28 am 
SON OF A GUN
SON OF A GUN
User avatar

Joined: Mon Nov 01, 2004 5:41 am
Posts: 11605
A* solves everything, wtf are you talking about?

:)


Top
  Profile  
 
 Post subject: Re: (Discussion) Pathfinding
PostPosted: Sat Oct 23, 2010 2:19 am 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
CrashTECH wrote:
A* solves everything, wtf are you talking about?

:)

Sure... =)

Hey, Dwood15... what's the story with your procedurally generated mazes?


Top
  Profile  
 
 Post subject: Re: (Discussion) Pathfinding
PostPosted: Mon Oct 25, 2010 1:32 pm 
Northwood
Northwood
User avatar

Joined: Sun Jul 15, 2007 6:37 pm
Posts: 2261
Location: No. 1 Thread Killer
Gadget wrote:
CrashTECH wrote:
A* solves everything, wtf are you talking about?

:)

Sure... =)

Hey, Dwood15... what's the story with your procedurally generated mazes?


I don't know what happened to them. They disappeared.

But I'd like to take the idea of a procedurally generated maze and display a map where each position in the array became a place on the map, I imagine that the old 2d games worked in a similar way...

I haven't worked on anything like that lately. Also, if you want to see a neat way to use pathfinding here's an application that I think is very cool.


Top
  Profile  
 
 Post subject: Re: (Discussion) Pathfinding
PostPosted: Mon Oct 25, 2010 6:02 pm 
SON OF A GUN
SON OF A GUN
User avatar

Joined: Mon Nov 01, 2004 5:41 am
Posts: 11605
Going to give Gadget a hard on here...

Go buy this book... I liked my AI class, hated the proff. He was kind of a jerk for no reason. (Clearly, I don't understand A* even though I used it for path finding in the game my group wrote during the previous semester for senior design... but I digress)


Top
  Profile  
 
 Post subject: Re: (Discussion) Pathfinding
PostPosted: Mon Nov 01, 2010 1:00 am 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
Quote:

Haha... are you kidding me?! I have the 1st and 2nd edition of that book! =)

A few other notable books (or perhaps just "the best" in an area) in my library, many of them gifts, include:
A 2nd ed of the Art of Programming by Knuth;
An early ed of the "Dragon Book" by Aho et al. *;
Two editions of Tanenbaums Operating Systems book;
An old conference manual with quite a bit of commentary by Dijkstra **;
Paradigms of Artificial Intelligence Programming by Norvig ***;
Combinatorial Optimization: Algorithms and Complexity by Papadimitriou & Steiglitz (yeah, I had to look that one up);
Algorithm Design by Jon Kleinberg and Éva Tardos;
On Lisp! by Paul Graham ****.

Plus, 50+ other textbooks in a variety of areas within CS, even a few on Kindle now! =)

Of course, I have a couple dozen language books... Most not nearly as useful as Guy Steele's Common Lisp book. =)

* This is probably the fastest way to determine if someone has potential. Show this book to someone and ask them the name of the book, if they don't answer "the dragon book", they're probably a "street programmer". Run away before they infect your mind with their thoughts! =)
** Honestly, I haven't had a chance to read any of it yet though.
*** A great "coding" example book... work the problems in this book and you'll be a 10x better programmer when you're finished! Yes, I hope to finish it someday!
**** Very different from your typical language book. As the name suggests, this book is about creating DSLs within Lisp to run On Lisp. Very well-written book, it's obvious why the guy became a multi-millionaire from programming.

Quote:
I liked my AI class, hated the proff. He was kind of a jerk for no reason. (Clearly, I don't understand A* even though I used it for path finding in the game my group wrote during the previous semester for senior design... but I digress)

I'm not saying that A* isn't a good choice; It's clearly not a case of A* done though!


Top
  Profile  
 
 Post subject: Re: (Discussion) Pathfinding
PostPosted: Sun Nov 07, 2010 2:55 am 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
Just for gits and shiggles, I decided to solve the original maze using Prolog. Yeah, the giant 4x5 maze that was originally posted. Hell, I even cheated a bit and labeled the maze locations:
Code:
a..bc
de..f
.g.hi
.jkl.

Then I spent forever writing something like 16 lines of code to solve the damn thing. I'll tell you write now, if the next assignment given to me is anywhere near this complex, I'll go postal for sure. Actually, only two lines of code "solve" the problem; The rest of it describes the maze.
Code:
start(a).
goal(c).
goal(f).
goal(i).

connected(a,d).
connected(d,e).
connected(e,g).
connected(g,j).
connected(j,k).
connected(k,l).
connected(l,h).
connected(h,i).
connected(i,f).
connected(f,c).
connected(c,b).

path(A,B):-connected(A,B).
path(A,B):-connected(A,C),path(C,B).

And here is SWI-Prolog solving this difficult problem. I'll win a Turing award someday for this... I just knows it.
Code:
[1] 1 ?- [maze],
[maze].
% maze compiled 0.00 sec, 1,764 bytes
true.

[1] 2 ?- start(X).
X = a.

[1] 3 ?- goal(X).
X = c ;
X = f ;
X = i.

[1] 4 ?- path(a,c).
true .

[1] 5 ?- path(a,f).
true .

[1] 6 ?- path(a,i).
true .

Take that Adak! Turbo C is for..... operating systems.


Top
  Profile  
 
 Post subject: Re: (Discussion) Pathfinding
PostPosted: Wed Nov 10, 2010 7:33 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
Problem variation: Instead of giving away the map/maze up front, what if we turned this into an online algorithm/problem?

We could create a client/server architecture (just a server function actually) and protocol for moving within the maze. The client would be told what moves are available, then tell the server the direction it wants to move. The server could track and/or print the move sequence and print the total number of moves after a client finds a goal.

If people are interested, I'll go ahead and create another thread. Of course, we should probably check to see if this doesn't already exist first...


Top
  Profile  
 
 Post subject: Re: (Discussion) Pathfinding
PostPosted: Thu Nov 11, 2010 2:56 am 
Northwood
Northwood
User avatar

Joined: Sun Jul 15, 2007 6:37 pm
Posts: 2261
Location: No. 1 Thread Killer
o u gadget. ;) I thought that I was clear in the rules that the array given was simply an example and the person was to solve any arrays/matrices that were in those bounds? :P


Top
  Profile  
 
 Post subject: Re: (Discussion) Pathfinding
PostPosted: Sun Nov 14, 2010 12:47 am 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
In the 5x5 array bounds? =)

The cool part about the client/server online algorithm approach is that the maze is unknown in advance, and if you create enough varied mazes, you would get a pretty good idea of how the different algorithms/solutions fair against each other.


Top
  Profile  
 
 Post subject: Re: (Discussion) Pathfinding
PostPosted: Sun Nov 14, 2010 4:57 pm 
Northwood
Northwood
User avatar

Joined: Sun Jul 15, 2007 6:37 pm
Posts: 2261
Location: No. 1 Thread Killer
Gadget wrote:
In the 5x5 array bounds? =)


In the OP:
Array is x >= 4 and y >= 4 size.
:wink:

Quote:
The cool part about the client/server online algorithm approach is that the maze is unknown in advance, and if you create enough varied mazes, you would get a pretty good idea of how the different algorithms/solutions fair against each other.


Perl could handle that server idea quite easily, and implement a HiRes timer pretty well.


Top
  Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 33 posts ]  Go to page 1, 2  Next

All times are UTC - 8 hours


Who is online

Users browsing this forum: No registered users and 2 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group

© 2014 Future US, Inc. All rights reserved.