Hello all, I've looked at the sample pages listed in the pathfinding for beginners thread, and yet I'm still having problems implementing my pathfinding. The following code returns a path, and I'm sure the total value is the shortest path.
Unfortunately, what it does is it uses all the horizontal distance first, and then travels diagonally. This creates a very unnatural form of movement. I was hoping someone could help me?
I am using the Chebyshev distance equation listed at
http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html#S7 to calculate the heuristic, I've checked to ensure that the G values are all being added properly and both forms of movement cost the same... What am I doing wrong?
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
| public void pathFind(Node target){
this.target = target;
open.add(node);
target.setG(0);
Node current = node;
Node min = null;
while(!open.isEmpty()){
for(int i=0; i<current.getNeighbours().size(); i++){
Node temp = current.getNeighbours().get(i);
if(!open.contains(temp) && !closed.contains(temp)){
open.add(temp);
temp.setParent(current);
temp.setG(current.getG() + current.getMovement());
calculateF(temp);
}
else if(open.contains(temp) && !closed.contains(temp)){
if(temp.getG() < current.getG()+current.getMovement()){
temp.setParent(current);
temp.setG(current.getG() + current.getMovement());
calculateF(temp);
}
}
}
open.remove(current);
closed.add(current);
min = open.get(0);
for(int i=0; i<open.size(); i++){
if(open.get(i).getF() < min.getF())
min = open.get(i);
}
current = min;
if(closed.contains(target)){
deconstruct();
break;
}
}
System.out.println("FINISHED");
}
public void calculateF(Node aNode){
int move = aNode.getStraight();
aNode.setH(move * Math.max(Math.abs(aNode.getCentreX()-target.getCentreX()), Math.abs(aNode.getCentreY()-target.getCentreY())));
aNode.setF(aNode.getG() + aNode.getH());
} |
