Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 8 of 8

Thread: A Pathfinding Story

  1. #1
    Junior Member
    Join Date
    Aug 2013
    Posts
    12
    My Mood
    Cheerful
    Thanks
    2
    Thanked 1 Time in 1 Post

    Default A Pathfinding Story

    Hi guys, I have a question about pathfinding methods. For now I am only interested in Tile Based pathfinding, which, as anyone who has broached the topic will know, is worlds easier.
    I have developed several pathfinding algorithms and some have had more success than others, but ultimately they are too inefficient.
    So I was wondering if some people could outline their own successful algorithms, so I can see what other ways people have come up with. Also if anyone has more general tips for optimising this process then please let me know,

    Thanks java pros


  2. #2
    Super Moderator
    Join Date
    Jun 2013
    Location
    So. Maryland, USA
    Posts
    5,520
    My Mood
    Mellow
    Thanks
    215
    Thanked 698 Times in 680 Posts

    Default Re: A Pathfinding Story

    Show or describe your own favorite algorithm and explain what you believe is inefficient about it.

  3. #3
    Junior Member
    Join Date
    Aug 2013
    Posts
    12
    My Mood
    Cheerful
    Thanks
    2
    Thanked 1 Time in 1 Post

    Default Re: A Pathfinding Story

    Well, my algorithm involves designating tiles on a grid to be 'updated'. It then goes through all the tiles that need to be updated and effectively 'spreads' across neighbouring tiles which it adds to the update list. The cycle then repeats until the flow reaches the target and the path can be traced back. I was just wondering if there were any drastically different approaches to the problem.

  4. #4
    Super Moderator
    Join Date
    Jun 2013
    Location
    So. Maryland, USA
    Posts
    5,520
    My Mood
    Mellow
    Thanks
    215
    Thanked 698 Times in 680 Posts

    Default Re: A Pathfinding Story

    Hmmm. Not sure I get your explanation.

    My maze generator and solver contains 'cells'. I assume those are like tiles. My cells have characteristics. I don't remember them all, but each of the 4 sides is either a wall or open, the cell is either on the solution path or not, it has either been visited or not, the possible exits remaining to be tried, etc. The cell's side characteristics are set on creation, the others are discovered and set by the solver.

    The solver starts at the beginning and crawls the puzzle as needed to find the exit, backtracking when reaching a dead end by following the path that has been pushed to a stack in reverse until finding a cell that has an exit that hasn't been explored. Not all cells in the maze have to be visited, only those needed to discover the solution.

    Is that any better than yours? Who knows?

  5. #5
    Junior Member
    Join Date
    Aug 2013
    Posts
    12
    My Mood
    Cheerful
    Thanks
    2
    Thanked 1 Time in 1 Post

    Default Re: A Pathfinding Story

    Haha, I think your right this would be a tricky topic to discuss, thanks for your explanation though, It does sound interestingly different.

  6. #6
    Senior Member
    Join Date
    Jul 2013
    Location
    Europe
    Posts
    666
    Thanks
    0
    Thanked 121 Times in 105 Posts

    Default Re: A Pathfinding Story

    You can simply use the Dijkstra Algorithm for pathfinding in tile maps since they are just bidirectional graphs where each tile is a node and adjacency of tiles is adjacency of nodes in the graph.

  7. The Following User Says Thank You to Cornix For This Useful Post:

    fatchance30 (April 16th, 2014)

  8. #7
    Junior Member
    Join Date
    Aug 2013
    Posts
    12
    My Mood
    Cheerful
    Thanks
    2
    Thanked 1 Time in 1 Post

    Default Re: A Pathfinding Story

    Thanks Cornix, I've been looking for just that kind of algorithm!

  9. #8
    Member
    Join Date
    Apr 2014
    Posts
    219
    Thanks
    8
    Thanked 2 Times in 2 Posts

    Default Re: A Pathfinding Story

    I like A* (A star) using the manhattan heuristic. This of course can only be applied to virtual type problem because a read device cannot teleport to unchecked locations.

    I suppose there is the conventional breadth and depth first search too. Then again I guess it depends on if you want to visit each node to ensure accuracy or disregard some that are assumed to be no benefit to you.

Similar Threads

  1. Replies: 4
    Last Post: January 21st, 2014, 10:36 AM
  2. My Story ... :)
    By ZekeQR in forum Member Introductions
    Replies: 3
    Last Post: April 18th, 2012, 02:53 AM
  3. Share your story with Java?
    By imicrothinking in forum The Cafe
    Replies: 6
    Last Post: October 25th, 2011, 06:32 AM
  4. A Star Pathfinding algorithm optimization
    By randomcracker in forum Algorithms & Recursion
    Replies: 4
    Last Post: May 18th, 2011, 11:11 PM
  5. My Story
    By M3ss1ah in forum Member Introductions
    Replies: 1
    Last Post: February 17th, 2011, 10:12 AM

Tags for this Thread