pathfinding en js

Version imprimable

21/05/2007, 15h46
arcanis

pathfinding en js

Bonjour!
Je développe un jeu en ligne fonctionnant à l'aide d'une carte 2D comportnt des cases de différents types (eau, montagne, forêt, herbe). J'aimerais savoir comment faire pour créer un algorithme simple de pathfinding en javascript.
Je me suis renseigné sur le A*, mais on dirait qu'il n'est pas possible de l'utiliser avec JS (ça ne m'étonne pas trop, en même temps :? ).
Et au pire, est-ce qu'un tel script existe en PHP?

Merci d'avance!
21/05/2007, 16h16
SpaceFrog

rien compris ... ???
tu peux expliciter un peu ?
21/05/2007, 20h00
arcanis

En fait voilà:
Un joueur possède un quota de déplacement de 9 (par exemple). Il faut qu'il se déplace de A vers B avec un chamin qui lui prendra le moins de déplacement possible.
Or:
- une plaine prend un déplacement
- une foret en prend 2
- une montagne 3
- une mer 999 (on ne peut pas passer)
Comment faire, donc, pour réussir à créer un script qui permettra de définir le chemin le moins "onéreux"? La carte est une grille, donc celà facilite peut-être les chose, je ne sais pas trop...
21/05/2007, 20h19
SpaceFrog

Javatwister ? t'es là ?
c'est un challenge pour toi ... :mouarf:
à moins que tu n'aies déja ça dans tes cartons ?
21/05/2007, 21h07
LEK

Pourquoi ce ne serait pas possible d'implémenter un tel algorithme en js? Le seul problème potentiel peut provenir de la grandeur et de la complexité de la matrice... Mis à part cela, ça à l'air d'être un algo largement implémentable en js !
21/05/2007, 21h48
javatwister

ben nan j'ai pas fait ça dans ma vie; mais c'est intéressant!

Salut,

Voici comment j'imagine ton algo. C'est pas abouti. Mais ça devrait
te permettre de faire des tests.

Toute la problématique se situe dans la fonction récursive findPath
bon courage :)

Code:

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
 
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
"http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
<title>Gestelle - Gestion de Tutelle</title>
<meta http-equiv="Content-Type" content="text/html;charset=utf-8">
<style type='text/css'>
div { width: 40px; height: 40px; text-align: center; float: left; border: 1px solid black; }
div.start { background-color: red; }
div.clearboth { clear: both; }
</style>
<script language='javascript' type='text/javascript'>
var MAPW = 20;
var MAPH = 10;
var map = "####################" +
          "####################" +
          "####################" +
          "########33333333####" +
          "#######133333#######" +
          "####11111222222#####" +
          "###11111111222222###" +
          "#####11111111111####" +
          "####################" +
          "####################";
 
var values = new Array();
 
function getMapValue(x, y) {
	var c = map.charAt(x + y * MAPW);
	if(c=='#') return 999;
	return c-0;
}
 
function findPath(x, y, v) {
    if(values[y][x]!=999) return; // a discuter
	n = getMapValue(x, y);
	if(v<n) return;
	values[y][x] = Math.min( values[y][x], v); // a discuter
	v = v - n;
        // à modifier, explorer une voie que si elle est non explorée ou 
        // qu'elle est plus honéreuse à ce stade
	if(x > 0) findPath( x - 1, y, v);
	if(y > 0) findPath( x, y - 1, v);
	if(x < MAPW-1) findPath( x + 1, y, v);
	if(y < MAPH-1) findPath( x, y + 1, v);
}
 
function initValues() {
	values = new Array();
	for(var y=0;y<MAPH;y++) {
		values[y] = new Array();
		for(var x=0;x<MAPW;x++) values[y][x] = 999;
	}
}
 
function showValues() {
	for(var y=0;y<MAPH;y++) for(var x=0;x<MAPW;x++) {
		var cl = new Array();
		if(x==0) cl[cl.length] = 'clearboth';
		if(y==PY && x==PX) cl[cl.length] = 'start';
		cl = cl.join(' ');
		document.write( "<div class='" + cl + "'>" + values[y][x] + "</div>");
	}
}
 
var PX = 10;
var PY = 5;
initValues();
findPath(PX, PY, 8);
showValues();
 
</script>
	</head>
 
	<body>
</body>
</html>

22/05/2007, 12h12
arcanis

merci!
Je vais voir comment l'utiliser.

(pour ceux que ça interesse, sinon, j'ai trouvée une implémentation php de astar sur la page http://pingouin.migrateur.free.fr/astar/astar.php.html)