Discussion :

[widguet]

Bonjour,
J'essaye de developper un algo qui crée un chemin entre 2 points
Mon algo ne plante pas, il finit la fonction mais ma liste chainée "path" n'est pas bonne. Et ce que je ne comprend pas c'est qu'à chaque fois que je modifie la liste chainée "Openlist" il me modifie aussi "Path"
Si vous pouvez m'aider merci

Code :

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
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
 
AStar(D3DXVECTOR2 start, D3DXVECTOR2 goal)
{
	bool quit=false;
	//The path
	node *Path = new node();
	Path->next=NULL;
	//The 2 list of nodes open and closed
	node *OpenList=new node();
	OpenList->next=NULL;
	node *ClosedList = new node();
	ClosedList=NULL;
 
	//pointer to the current node
	node *Current = new node();
	Current=OpenList;
 
	//pointer to the best node
	node *Best=new node();
	Best=NULL;
 
	//create the start node
	node *Start=new node();
	Start->Position=start;
	Start->g=0;
	Start->h=DetermineH(Start->Position,goal);
	Start->h=DetermineF(Start->g,Start->h);
	Start->next=NULL;
 
	//set the start point to the past
	Path=Start;
 
	//add the start node to the open list
	OpenList=Start;
 
	while(quit==false)
	{
		Current=OpenList;
		//find the closest node to the goal
		//if Best= NULL then define the first node as the best one
		if(Best==NULL)
		{
			Best=Current;
		}
		else
		{
			//else loop through all the nodes
			while(Current!=NULL)
			{			
				if(Current->h<Best->h)
				{
					Best=Current;
				}
				Current=Current->next;
			}
		}
 
		//find the path
		if(Best->Position==goal)
		{
			quit=true;
			return 1;
		}
 
		//failed
		if(OpenList==NULL)
		{
			quit=true;
			return -1;
		}
 
		//find connected node to the best node
		int x=1;
		int y=0;
 
		for(int i=0;i<3;i++)
		{
			//pointer to a connected node
			node *connected=new node();
			connected->Position=D3DXVECTOR2(Best->Position.x+x,Best->Position.y+y);
			connected->h=DetermineH(connected->Position,goal);
			connected->next=NULL;
 
			Current=OpenList;
			//determine if the node is in the openlist
			if(Current->next==NULL)
			{
				//found it in the open list
				if(Current->Position==connected->Position)
				{
					//check if the path is more efficient
					if(connected->h<Best->h)
					{
						//add the new node to the open list
						AddTotheEnd(Path,connected);
					}
				}
				else
				{
						//add the node to the openlist
						AddTotheEnd(OpenList,connected);
				}
			}
			else
			{
				while(Current!=NULL)
				{
					//found it in the open list
					if(Current->Position==connected->Position)
					{
						//check if the path is more efficient
						if(connected->h<Best->h)
						{
							//add the new node to the open list
							AddTotheEnd(Path,connected);
						}
					}
					else
					{
							//add the node to the openlist
							AddTotheEnd(OpenList,connected);
					}
					Current=Current->next;
				}
			}
 
			if(x==1 && y==0)
			{
				x=0;
				y=1;
			}
			else
			{
				if(x==0 && y==1)
				{
					x=1;
					y=1;
				}
			}
		}
	}
	return 0;
}

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
AddTotheEnd(node *List, node *Toadd)
{
	node *curr=new node();
 
	if (List != NULL)
	{
		curr = List;
	}
 
	//loop through allthe nodes
	while (curr->next!= NULL)
	{
		curr = curr->next;
	}
 
	//add the node to the list
	curr->next=Toadd;
	Toadd->next=NULL;
}

[bacelar]

Pour moi, c'est du très mauvais C++, mais du C++ quand même

1- les new c'est bien gentil mais faudrait penser au delete de temps en temps car la mémoire n'est pas infini.
2- faire des new sur des affectations de variables pointeurs, puis la ligne d'après l'assigner à NULL : à quoi bon cette création superfétatoire ?
3- des pointeurs en veux-tu en voilà , moins de pointeur égale un code plus maintenable et plus compréhensible (voir l'explication du problème initial à la fin de la réponse

4-

Code :

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

1
2
    Start->h=DetermineH(Start->Position,goal);
    Start->h=DetermineF(Start->g,Start->h);

Ou c'est une erreur d'étourderie (Start->h sur 2 lignes), ou c'est un magnifique exemple de programmation par effet de bord. Cela serait l'un des plus beaux spécimens que j'aurais vu.

réponse au problème initial

Code :

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

1
2
3
4
5
    //set the start point to the past
    Path=Start;
 
    //add the start node to the open list
    OpenList=Start;

Path est un pointeur, OpenList aussi et Start aussi. Donc, le ci-dessus est égale à Path = OpenList = Start;
Comme c'est des pointeurs, si vous modifiez la "chose" pointé par Path, vous changez la "chose" pointé par OpenList.

C'est la mécanique de base des pointeurs qui ne sont que des adresses mémoires. Si vous modifiez la mémoire pointé, tous les pointeurs qui pointent sur cette zone mémoire seront automatiquement "affectés" car ils pointent physiquement sur la même chose.

En résumé, faire toujours un code simple avec des concepts que l'on maîtrise. Et widguet ne maîtrise ni la gestion mémoire, ni les pointeurs et le code semble très peu maintenable par des effets de bord.

[hiko-seijuro]

Bonjour,

il pourrait être intéressant pour toi de consulter le tuto suivant : http://khayyam.developpez.com/articles/algo/astar/