Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (482)
Games in Android Showcase (110)
games submitted by our members
Games in WIP (548)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  A* Pathfinding question  (Read 4970 times)
0 Members and 1 Guest are viewing this topic.
Offline dayrinni

Junior Member





« Posted 2007-08-23 06:46:06 »

Hi,

I've been working on this for several hours now and it is time to head to bed. I decided to post up my current attempt at writing A* where the cost is 0 for all nodes.

Currently, when I run this, the solution (which is the open list), contains every single node that the algorithm looked at. I am going by this description of the algorithm:
http://ai-depot.com/Tutorial/PathFinding.html
Though either I am not understanding this properly or that example is flawed...

I know my algorithm is reaching the indicated node because it leaves a single node untouched...
So I need to know how to remove unwanted nodes from the list as I go.

Here is my code for the algorithm. If you require the entire program let me know.

The filled part tells the program to draw a filled rectangle as opposed to an outline of one.

Thanks for any assistance.

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
57  
58  
59  
60  
61  
62  
63  
64  
65  
66  
67  
68  
69  
70  
71  
72  
73  
74  
public static void pathFind(PathWindow window)
   {

     
      Node startNode = window.getColumns().get(0).getNodeList().get(0);
      int cols = window.getColumns().size();
      int rows = window.getColumns().get(0).getNodeList().size();
      Node endNode = window.getColumns().get(cols-1).getNodeList().get(rows-1);
     
      LinkedList<Node> openList = new LinkedList<Node>();
     
      openList.add(startNode);
     
      while(openList.size() > 0)
      {
         Node currentNode = openList.poll();
         
         //currentNode.setFilled(true);
       
         //If we are at the end.
        if(currentNode.equals(endNode))
         {
            //Add the current node back in since we removed it above.
           openList.add(currentNode);
            break;
         }
         
         //Successors
       
         if(currentNode.getAboveNode() != null)
         {
            if(openList.contains(currentNode.getAboveNode()) == false)
            {
               openList.add(currentNode);
               openList.add(currentNode.getAboveNode());
            }
         }
         if(currentNode.getUnderNode() != null)
         {
            if(openList.contains(currentNode.getUnderNode()) == false)
            {
               openList.add(currentNode);
               openList.add(currentNode.getUnderNode());
            }
         }
         if(currentNode.getLeftNode() != null)
         {
            if(openList.contains(currentNode.getLeftNode()) == false)
            {
               openList.add(currentNode);
               openList.add(currentNode.getLeftNode());
            }
         }
         if(currentNode.getRightNode() != null)
         {
            if(openList.contains(currentNode.getRightNode()) == false)
            {
               openList.add(currentNode);
               openList.add(currentNode.getRightNode());
            }
         }
         
      }
     
      System.out.println("openlist is:\n" + openList);
     
      //set all these nodes to filled.
     for(int i = 0;i<openList.size();i++)
      {
         openList.get(i).setFilled(true);
      }
     
      window.repaint();
}
Offline keldon85

Senior Member


Medals: 1



« Reply #1 - Posted 2007-08-23 16:22:23 »

Without looking at the code; change the cost to 1.

Offline dayrinni

Junior Member





« Reply #2 - Posted 2007-08-23 17:46:26 »

Without looking at the code; change the cost to 1.

How would this change the affects? As they are all 1's so if I am at a current node with a current cost of 10 and then all the nodes around me are cost 1, they're all equal.

Thanks.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline keldon85

Senior Member


Medals: 1



« Reply #3 - Posted 2007-08-23 18:34:29 »

If the cost is 0 then every path is the shortest path. For an A* search you should also keep a closed list as well so that you don't add nodes you've already processed. Also out of curiosity what is the application? With edges of equal cost A* isn't always the best option - although coding it is easy.

Offline dayrinni

Junior Member





« Reply #4 - Posted 2007-08-23 18:49:54 »

If the cost is 0 then every path is the shortest path. For an A* search you should also keep a closed list as well so that you don't add nodes you've already processed. Also out of curiosity what is the application? With edges of equal cost A* isn't always the best option - although coding it is easy.

Thanks for the reply. It's for a game I'm making. I'm just trying to get the thing to work in any way and then I will be adding onto it. I'll try adding the closed list.

I'll let you know soon...
Offline dayrinni

Junior Member





« Reply #5 - Posted 2007-08-23 19:12:28 »

Your suggestion worked and now I have basic pathfinding!

Thanks a lot.

On a side note, this turned out to be a lot easier than I was thinking it would be. I've put this off for over a year. It only took me about 6 hours to do (which includes reading tutorials, forums and other web pages). Thanks again for your help.
Offline dayrinni

Junior Member





« Reply #6 - Posted 2007-08-24 06:05:58 »

Hello,

I have another question regarding this.

Given a map with a nice portion of walls so the path is a bit complex and all the costs of the nodes are 1, will A* come up with the same path every time (assume nothing changes except you want to calc another path)?

I'm trying to decide if I can afford the server to send the path to all the clients or have the clients do it themselves. It's really a bandwidth question.

Thanks!
Offline keldon85

Senior Member


Medals: 1



« Reply #7 - Posted 2007-08-24 06:57:43 »

If you are at the same source/dest then the paths will be the same unless the order of the lists change. You would probably want the clients to calculate the path and not the server, there's just no need to do it that way.

Offline dayrinni

Junior Member





« Reply #8 - Posted 2007-08-24 17:26:32 »

If you are at the same source/dest then the paths will be the same unless the order of the lists change. You would probably want the clients to calculate the path and not the server, there's just no need to do it that way.

This is what I'm thinking...

I can have the client calculate the path and send it to the server. The server will check it to ensure it is not fake (going through walls, etc) and then tell all the other clients to generate the path. Then the server will tell the indicated character to move on the server. I have the server move all of the paths as well so that the clients can not do bogus things if they get out of synced. I send an update every 10 seconds. This sounds like a reasonable approach that won't suck up the CPU of the server but keep things synced as well as secure to a good extent.

By the way, thanks for replying - you've been most helpful Smiley
Offline JAW

Senior Member


Medals: 2



« Reply #9 - Posted 2007-09-14 08:22:26 »

Using A* with a path cost of 0 can be used as a "flood fill" algorithm to get areas instead of paths. If you want the forest, take any node and run a search where forest nodes cost 0 and all others cost 1. All 0 nodes will go in the list and then you have a list of all connected forest nodes.

General A* applications like this are described in the AI Game Programming Books. You can do a lot of stuff with A*. But for finding a single path, you'll always need a cost. Otherwise the heuristic wont work which aims to keep the search space limited.

-JAW
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

atombrot (28 views)
2014-08-19 09:29:53

Tekkerue (25 views)
2014-08-16 06:45:27

Tekkerue (23 views)
2014-08-16 06:22:17

Tekkerue (15 views)
2014-08-16 06:20:21

Tekkerue (22 views)
2014-08-16 06:12:11

Rayexar (61 views)
2014-08-11 02:49:23

BurntPizza (39 views)
2014-08-09 21:09:32

BurntPizza (31 views)
2014-08-08 02:01:56

Norakomi (37 views)
2014-08-06 19:49:38

BurntPizza (67 views)
2014-08-03 02:57:17
List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06

List of Learning Resources
by SilverTiger
2014-07-31 11:54:12

HotSpot Options
by dleskov
2014-07-08 01:59:08
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!