pathfinding en js

**arcanis** · 21/05/2007, 16h46

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!

**SpaceFrog** · 21/05/2007, 17h16

rien compris ... ???
tu peux expliciter un peu ?

**arcanis** · 21/05/2007, 21h00

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...

**SpaceFrog** · 21/05/2007, 21h19

Javatwister ? t'es là ?
c'est un challenge pour toi ...

à moins que tu n'aies déja ça dans tes cartons ?

**LEK** · 21/05/2007, 22h07

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 !

**javatwister** · 21/05/2007, 22h48

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

**marcha** · 21/05/2007, 23h55

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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>

**arcanis** · 22/05/2007, 13h12

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)

pathfinding en js

JavaScript

Discussions similaires

Partager

Partager