This discussion is archived
10 Replies Latest reply: Mar 4, 2010 6:04 PM by 843853 RSS

Maze Path Finder

843853 Newbie
Currently Being Moderated
Hi!!! I am making a simple RTS game and I have some problems with path finding. I have read many articles on this subjects but didn´t understand the idea of the algorithsm or there was not enough info on how it works...

The best article I read is on this url: http://www.codeproject.com/KB/recipes/mazesolver.aspx

I have an int[][] array storing 0(for emty spaces) and 1(for walls). It´s 100x100 and the algorithsm should be able to trace diagonals.

I tryed coding myself some kind of tree-uilder and tree-explorer which usead to check every single path to the end, but it didn´t work.
Can you help me plz?

Thank you so much!
  • 1. Re: Maze Path Finder
    796262 Newbie
    Currently Being Moderated
    CPFrn wrote:
    Hi!!! I am making a simple RTS game and I have some problems with path finding. I have read many articles on this subjects but didn´t understand the idea of the algorithsm or there was not enough info on how it works...
    Then ask a specific question about what you didn't understand. What part of the algorithm didn't you understand?
    The best article I read is on this url: http://www.codeproject.com/KB/recipes/mazesolver.aspx
    Okay, and what did you learn from the article?
    I have an int[][] array storing 0(for emty spaces) and 1(for walls). It´s 100x100 and the algorithsm should be able to trace diagonals.
    And does it?
    I tryed coding myself some kind of tree-uilder and tree-explorer which usead to check every single path to the end, but it didn´t work.
    How didn't it work? What specifically did you try? Posting an [SSCCE |http://sscce.org] might help.
    Can you help me plz?
    "plz" is not a word.
  • 2. Re: Maze Path Finder
    791266 Explorer
    Currently Being Moderated
    CPFrn wrote:
    I tryed coding myself some kind of tree-uilder and tree-explorer which usead to check every single path to the end, but it didn´t work.
    How did it fail?
    Can you help me plz?
    How? I guess that nobody here wants to implement it for you.
  • 3. Re: Maze Path Finder
    843853 Newbie
    Currently Being Moderated
    I love this forum. It´s full of people willing to help :D
    I didn´t want to have it implemented by you, just some help. But well, somehow I expected this from this comunity
    Tanks for nothing
  • 4. Re: Maze Path Finder
    796262 Newbie
    Currently Being Moderated
    If you had simply answered my questions and made an honest effort, I would have loved to help you with this problem.

    Before you post again, maybe you should learn [How To Ask Questions The Smart Way|http://catb.org/~esr/faqs/smart-questions.html] . Until then, good luck programming with that attitude.
    Tanks for nothing
    Can I get airplanes for nothing? How about some boats?
  • 5. Re: Maze Path Finder
    843853 Newbie
    Currently Being Moderated
    Can I get airplanes for nothing? How about some boats? 
    How about some cocks? I know you would love that
  • 6. Re: Maze Path Finder
    796262 Newbie
    Currently Being Moderated
    CPFrn wrote:
    How about some [edited]? I know you would love that
    Is it a full moon or something? What is with people today?

    Up until this point, I was still completely willing to help you (your problem actually seems like it might be interesting). All you had to do was ask a specific question and explain your problem in a little more detail. Instead, this. Wow. Just, wow.
  • 7. Re: Maze Path Finder
    jwenting Journeyer
    Currently Being Moderated
    kevinaworkman wrote:
    CPFrn wrote:
    How about some [edited]? I know you would love that
    Is it a full moon or something? What is with people today?
    Nothing that's not been the case with schoolkids for most of a decade. They're lazy, rude, and have an overinflated sense of self importance and entitlement.
  • 8. Re: Maze Path Finder
    843853 Newbie
    Currently Being Moderated
    If the maze is grid-based, try this:
    public boolean findMyWay(Point current, Point destination, Stack<Point> path) {
      if(current.x==destination.x&&current.y==destination.y) {
        path.put(destination);
        return true;
      }
      else {
        Point left = new Point(current.x+1, current.y);
        if(isRearchable(left)) {
          path.push(current);
          if(findMyWay(left, destination, path)) {
            return true;
          }
          path.pop();
         // and right: current.x-1
         // and up: current.y-1
         // and down: current.y+1
        }
        return false;
      }
    }
    This only helps you find a way to the destination but cannot be ensured it's the best way. For best way, once you reach the destination, do not return true. Instead you should remember the path, save it to another place. and go back to previous grid and continue run. Once the whole calling end, you just need to find the stack which has minimum points in it.

    This algorithm could be expanded to node-based scenario. The difference is you need another stack to remember the distance between nearest reachable nodes. I suspect popular RTS is grid-based or node-based no matter it looks like point-based (unit has a float x and y). Because grid/node-base search is much faster and easier. One clue is when I open/save a Warcraft 3 map in editor, it always take some time to compile the map and one of the message looks 'calculating path'. If it's just a map, why does it need to calculate path? I suspect it's creating nodes which is used for path finding in the game.

    Edited by: qqsu_azure on Mar 4, 2010 1:39 AM
  • 9. Re: Maze Path Finder
    796262 Newbie
    Currently Being Moderated
    Something tells me the OP is looong gone by now...
  • 10. Re: Maze Path Finder
    843853 Newbie
    Currently Being Moderated
    kevinaworkman wrote:
    Something tells me the OP is looong gone by now...
    :) But that doesn't block other guys post their own opinions on an interesting topic.