Dijkstra's Algo
Ik ben al vet lang bezig met een simpel scriptje en ik denk dat ik een klein beetje hulp nodig heb voor het afronden ermee :P.
Nou probeer ik een script te maken die de kortste route vind.
Nu is het rechtstreeks van punt A naar punt B vinden makkelijk, door de twee posities van elkaar te trekken: possitie_diff(x,y) = positie_puntA(x,y)-positie_puntB(x,y).
Maar het word moeilijker om de kortste route te berekenen wanneer er obstakels erbij zitten.
Op deze plaatje (Link) heb ik 2 situaties geschetst.
Rode X = Begin punt
Blauwe X = Eind punt
donker blauw gevulde blok = muur/obstakel
Mijn gemaakte code werkt goed tot het een obstakel tegen komt. Dan gaat het in een hele lange for loop 1 stapje achteruit en dan 1 stapje vooruit etc.
Nu zou ik ook niet echt weten hoe ik dit kan oplossen XD.
Code van Santhe op http://www.test.santhe.nl/game.php heb ik ook geprobeerd maar die doet heel erg vaag XD. (zie me vorige topic http://www.phphulp.nl/forum/showtopic.php?cat=2&id=60268)
Gewijzigd op 01/01/1970 01:00:00 door Kumkwat Trender
Jezpur schreef op 11.06.2009 19:01:
Had je dan niet beter in dat topic verder kunnen gaan?
Nee, dit is een heel ander probleem en een heel andere opdracht. Het is logisch dat mijn script hier niet werkt.
Quote:
code weggezet omdat het anders een hele lange pagina werd
Nu werkt dit wel
Code (php)
en deze niet doordat het steeds herhaald word:
Code (php)
help??
Edit:
output van de eerst:
[4.4][4.4]
Array ( [0] => 1 [1] => 1 [2] => 1 [3] => 1 )
Array ( [0] => 4 [1] => 3 [2] => 2 [3] => 1 )
1 - 4
1 - 3
1 - 2
1 - 1
Gewijzigd op 01/01/1970 01:00:00 door Kumkwat Trender
Ik zal dit eens bekijken; wie weet kan ik dat ook nog nodig hebben.
Anders moet je eens naar het A* algorythme kijken,,
heb k 3 weken geleden nog uitgewerkt in C#
http://en.giswiki.net/wiki/Dijkstra's_algorithm
Gewijzigd op 01/01/1970 01:00:00 door Emmanuel Delay
Op welke manier wil je dit gaan oplossen,
Moet het echt Dijkstra's algoritme zijn, of moet je de A star hebben?
Ik wil het opzich best voor je proberen, alleen je moet even de gegevens geven die je gebruikt voor het grid.
Ik wil per sé eigenlijk een php versie dus heb ik van een js script dat ik ergens op internet had gevonden proberen te veranderen in php. Alleen is dat niet echt goed gegaan..
Zo ziet de php eruit dat ik gemaakt heb
Code (php)
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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
<?php
error_reporting(E_ALL);
class AStar{
public function __construct($grid,$start,$einde) {
$this->grid = $grid;
$this->start = $start;
$this->einde = $einde;
$rows = 20;
$cols = 20;
$this->rows = strlen($rows);
$this->cols = strlen($cols);
$this->limiet = strlen($cols)*strlen($rows);
$this->einde = $einde;
$this->einde = $einde;
$this->Path();
}
public function Grid($x,$y){
return $this->grid[$y][$x]===0;
}
public function Node($Parent,$Pp){
foreach($Pp as $z=>$Point) {
if($z=='x') {
$Pointx = $z;
} elseif($z=='y') {
$Pointy = $z;
}
}
return array(
'Parent' => $Parent,
'value' => $Pointx+($Pointy*$this->cols),
'x' => $Pointx,
'y' => $Pointy,
'f' => 0,
'g' => 0
);
}
public function Path(){
$Start =$this->Node(null,array('x'=>$this->start[0],'y'=>$this->start[1]));
$StartOpen =$this->Node(null,array('x'=>$this->start[0],'y'=>$this->start[1]));
$Goal =$this->Node(null,array('x'=>$this->einde[0],'y'=>$this->einde[1]));
$AStar =Array($this->limiet);
$Open =Array($Start);
$Closed[] ='';
$result[] ='';
$Successors = '';
$Node = '';
$Path = '';
print_r($Open);
$length =strlen($Open);
while($length){
$max=$this->limiet;
$min=-1;
for($i=0;$i<$length;$i++){
if($StartOpen['f'][$i]<$max){
$max=$StartOpen['f'][$i];
$min=$i;
}
};
$Node=array_splice($StartOpen,$min);
if($Node['value']===$Goal['value']){
array_push($Closed,$Node);
$Path=$Closed[1];
do {
array_push($result,$Path['x'],$Path['y']);
}
while($Path=$Path['Parent']);
$AStar=$Closed;
array_reverse($result);
} else {
$Successors=$this->Successors($Node['x'],$Node['y']);
for($i=0;$i<strlen($Successors);$i++){
$Path=$this->Node($Node,$Successors[$i]);
if($Path['value']){
$Path['g']=$Node[3]+$this->Manhattan($this->Successors[$i],$Node);
$Path['f']=$Path[3]+$this->Manhattan($this->Successors[$i],$Goal);
array_push($Open,$Path);
};
};
array_push($Closed,$Node);
};
};
return $result;
}
function Successors($x,$y){
echo $y;
$N =$y-1;
$S =$y+1;
$E =$x+1;
$W =$x-1;
$N2 =$N>-1&&$this->Grid($x,$N);
$S2 =$S<$this->rows&&$this->Grid($x,$S);
$E2 =$E<$this->cols&&$this->Grid($E,$y);
$W2 =$W>-1&&$this->Grid($W,$y);
$result[] ='';
if($N2) {
array_push($result,array('x'=>$x,'y'=>$N));
}
if($E2) {
array_push($result,array('x'=>$E,'y'=>$y));
}
if($S2) {
array_push($result,array('x'=>$x,'y'=>$S));
}
if($W2) {
array_push($result,array('x'=>$W,'y'=>$y));
}
return $result;
}
public function Manhattan($point,$goal){
return abs($point[0]-$goal[0])+abs($point[1]-$goal[1]);
}
}
function GridGenerator($width, $height){
$result = Array($height);
for($i = 0; $i < $height; $i++) {
$result[$i] = Array($width);
for($j = 0; $j < $width; $j++) {
$result[$i][$j] = ($j * $i) % 7 ? floor(rand(0,1) * 200) % 2 : 0;
}
};
return $result;
}
$gb = GridGenerator('20','20');
$sb = array(ceil(rand() * (20 * 20)),0);
$random = true;
$l = 20;
for($i = 0; $i < 20; $i++) {
for($k = 0; $k <$l; $k++) {
if($gb[$i][$k] !== 0) {
} else {
if($random && $sb <= $i + ($k * $l)) {
$random = false;
} else {
$bot = new AStar($gb,$sb,$sb);
}
}
}
}
?>
error_reporting(E_ALL);
class AStar{
public function __construct($grid,$start,$einde) {
$this->grid = $grid;
$this->start = $start;
$this->einde = $einde;
$rows = 20;
$cols = 20;
$this->rows = strlen($rows);
$this->cols = strlen($cols);
$this->limiet = strlen($cols)*strlen($rows);
$this->einde = $einde;
$this->einde = $einde;
$this->Path();
}
public function Grid($x,$y){
return $this->grid[$y][$x]===0;
}
public function Node($Parent,$Pp){
foreach($Pp as $z=>$Point) {
if($z=='x') {
$Pointx = $z;
} elseif($z=='y') {
$Pointy = $z;
}
}
return array(
'Parent' => $Parent,
'value' => $Pointx+($Pointy*$this->cols),
'x' => $Pointx,
'y' => $Pointy,
'f' => 0,
'g' => 0
);
}
public function Path(){
$Start =$this->Node(null,array('x'=>$this->start[0],'y'=>$this->start[1]));
$StartOpen =$this->Node(null,array('x'=>$this->start[0],'y'=>$this->start[1]));
$Goal =$this->Node(null,array('x'=>$this->einde[0],'y'=>$this->einde[1]));
$AStar =Array($this->limiet);
$Open =Array($Start);
$Closed[] ='';
$result[] ='';
$Successors = '';
$Node = '';
$Path = '';
print_r($Open);
$length =strlen($Open);
while($length){
$max=$this->limiet;
$min=-1;
for($i=0;$i<$length;$i++){
if($StartOpen['f'][$i]<$max){
$max=$StartOpen['f'][$i];
$min=$i;
}
};
$Node=array_splice($StartOpen,$min);
if($Node['value']===$Goal['value']){
array_push($Closed,$Node);
$Path=$Closed[1];
do {
array_push($result,$Path['x'],$Path['y']);
}
while($Path=$Path['Parent']);
$AStar=$Closed;
array_reverse($result);
} else {
$Successors=$this->Successors($Node['x'],$Node['y']);
for($i=0;$i<strlen($Successors);$i++){
$Path=$this->Node($Node,$Successors[$i]);
if($Path['value']){
$Path['g']=$Node[3]+$this->Manhattan($this->Successors[$i],$Node);
$Path['f']=$Path[3]+$this->Manhattan($this->Successors[$i],$Goal);
array_push($Open,$Path);
};
};
array_push($Closed,$Node);
};
};
return $result;
}
function Successors($x,$y){
echo $y;
$N =$y-1;
$S =$y+1;
$E =$x+1;
$W =$x-1;
$N2 =$N>-1&&$this->Grid($x,$N);
$S2 =$S<$this->rows&&$this->Grid($x,$S);
$E2 =$E<$this->cols&&$this->Grid($E,$y);
$W2 =$W>-1&&$this->Grid($W,$y);
$result[] ='';
if($N2) {
array_push($result,array('x'=>$x,'y'=>$N));
}
if($E2) {
array_push($result,array('x'=>$E,'y'=>$y));
}
if($S2) {
array_push($result,array('x'=>$x,'y'=>$S));
}
if($W2) {
array_push($result,array('x'=>$W,'y'=>$y));
}
return $result;
}
public function Manhattan($point,$goal){
return abs($point[0]-$goal[0])+abs($point[1]-$goal[1]);
}
}
function GridGenerator($width, $height){
$result = Array($height);
for($i = 0; $i < $height; $i++) {
$result[$i] = Array($width);
for($j = 0; $j < $width; $j++) {
$result[$i][$j] = ($j * $i) % 7 ? floor(rand(0,1) * 200) % 2 : 0;
}
};
return $result;
}
$gb = GridGenerator('20','20');
$sb = array(ceil(rand() * (20 * 20)),0);
$random = true;
$l = 20;
for($i = 0; $i < 20; $i++) {
for($k = 0; $k <$l; $k++) {
if($gb[$i][$k] !== 0) {
} else {
if($random && $sb <= $i + ($k * $l)) {
$random = false;
} else {
$bot = new AStar($gb,$sb,$sb);
}
}
}
}
?>
En zo ziet de werkende Js script eruit: Klik
Ik heb het gevoel dat ik een klein ding verkeerd doe waardoor het net verkeerd de bocht gaat. Hopelijk dat iemand het ziet.
@Emmanuel die php voorbeeld dat op dat pagina staat is een beetje raar, ik heb hem getest maar er komt wat raars uit steeds.
Gewijzigd op 01/01/1970 01:00:00 door Kumkwat Trender
bedoel je die link? Link werkt bij mij ^^
Is weer zo een provider die zijn DNS niet correct heeft.
Moet ik weer allerlei omwegen doen voordat ik er bij kan.
Edit: DNS moet vier lagen diep voordat je een ip-adres van een DNS server krijgt. Hopeloos is dat.
devpro.it. 82038 IN NS ns4.areaserver.it.
devpro.it. 82038 IN NS ns2.areaserver.it.
areaserver.it. 81681 IN NS murdock.tiscali.com.
areaserver.it. 81681 IN NS barakus.tiscali.com.
tiscali.com. 164143 IN NS sns.tiscali.it.
tiscali.com. 164143 IN NS ns.tiscalinet.it.
tiscali.it. 82068 IN NS sns.tiscali.it.
tiscali.it. 82068 IN NS ns.tiscalinet.it.
sns.tiscali.it. 82068 IN A 195.130.225.129
ns.tiscalinet.it. 10789 IN A 195.130.224.18
Gewijzigd op 01/01/1970 01:00:00 door - SanThe -
alleen loopt deze vast na 5 kliks of zo :P
http://albertosyrup.110mb.com/astar.html
Edit:
Ow het loopt pas vast als je snel achter elkaar klikt
Gewijzigd op 01/01/1970 01:00:00 door Kumkwat Trender
Maar ik ben na wat aparte handelingen toch op de eerste link beland.
Ziet er netjes uit.
maar ik heb de eerste gekozen omdat het wat simpeler opgebouwd was.
Iemand nog suggesties waarom mijn code het verkeerd doet :(
Alle gegeven links blijken te werken..