pathfinding A*
15 sujets de 1 à 15 (sur un total de 19)
- 1
- 2
-
Bonjour,
Sa fais plus d’un mois que je recherche un code source exploitable et surtout compréhensible pour créer un pathfinding A* mais limité, Se que je recherche à faire (sous hollywood
)recherche du chemin entre 2 tuiles au coord de départ XTuile1,Ytuile1 et coord de destination XTuile2, Ytuile2
Le problème est que je suis limité, je m’explique:
le chemin ne peut être défini qu’horizontalement ou verticalement (pas oblique, pas de direction diagonale) et limité à 3 changements d’état, ex:
2 verticale et 1 horizontale ou 2 horizontale et 1 verticale.
A la fin de la recherche, une fois le chemin le plus court trouver, je dois dessiner le chemin.
Qui parmis nos développeur les plus caler peuvent m’aider, se qu’il me faudrait, c’est pas une source objet avec 10 procédures récursives mais une seul et même fonction histoire de comprendre la chronologie, en fait je veux comprendre le cheminement pour arriver à créé cet algo A star.
Des sources, j’en ai à la pelle mais j’y comprend rien… c’est pour le jeu de tarzin, il nous manque que sa et hop, vous aurez un nouveau jeu pour Aos/Morphos
Merci de votre aide (à la fin, je filerai le code source hollywood évidement, comme je le fait habituellement)
Tout me semble très bien expliqué ici:
http://theory.stanford.edu/~amitp/GameProgramming/
A ceci près que c’est en anglais et très long
putain… encore de l’anglais lol
J’en ai pour 1 ans là :sweat:
Mais sa m’a l’air quand même vachement mieux expliquer que les sites de bruns que j’ai visité
Long, mais après tu masterise!
Bon, déjà je sais que je dois utiliser la distance de Manhattan puisqu’elle exploite que les lignes verticales et horizontale, c’est déjà un bon début, j’ai une formule:
Distance=(Xtuile2-Xtuile1)+(Ytuile2-Ytuile1)
On dirait un calcule de vecteur… Mais qu’est-ce que j’en fais de cette formule?!? bon, j’y pige pas grand chose, si parmis vous, il y a des idées, se serais sympa de m’en faire part.
Bon, il faut de toute façon un tableau contenant les solutions, enfin je crois.
La valeur de cette formule devrait me donner le nombre de déplacement maxi. Dur dur la vie
Ok, je commence à comprendre le principe, en tous cas, l’animation sur wiki est excellent et la je pige mieux, je pensé qu’il fallait effectué un balayage de haut en bas de la table, en fait, il avance peux par peu vers la destination finale, j’ai réussi à trouver un code LUA, mon dieu qu’il est dure à traduire, mais grâce à toi j’ai pigé le concept, maintenant il faut que je traduise pour que sa fonctionne via hollywood.
J’ai pas tout pigé, mais sa commence à s’éclaircir
Merci
Je te tiens au courant de mes avancés
Vu!
Excellent, le code sur dropbox du pathfinding est un code pure LUA, j’ai réussi à choper sa sur extremelua, je pense qu’il n’y a pas grand chose à modifier, je suis dessus depuis 1 mois lol, bon, pour le code lua je l’ai trouvé que le 21.06.11, j’ai imprimer toutes les docs sur le pathfinding, je préfère le papier aux navigateurs, je trouve sa plus simple lors de recherche, t’inkiète je trouverai, d’ailleurs, si j’y arrive, on pourra exploiter se code pour d’autres choses
@Yomgui: tu va réussir à me faire cramer une ramette de papier lol, merci pour le coup de mainBonne nouvelle:
Jalih (un excellent programmeur sous holly) a réussi (et rapidement) à convertir un code LUA de pathfinding A* en code Hollywood (il a mis 20 minutes et moi je suis dessus depuis 1 mois lol)
Voici le code et merci au p’tit jalih
; Hollywood port of the
;
; A* algorithm For LUA
; Ported To LUA by Altair
; 21 septembre 2006
;
;
; Ported to Hollywood by jalih, it took 20 mins and two beers.
;
; Bugs are mine naturally.
;
;
Function CalcMoves(mapmat, px, py, tx, ty)
Local openlist = {}
Local closedlist = {}
Local listk = 0
Local closedk = -1
Local tempH = Abs(px - tx) + Abs(py - ty)
Local tempG = 0
Local xsize = ListItems(mapmat[0]) - 1
Local ysize = ListItems(mapmat) - 1
Local curbase = {}
Local basis = 0
InsertItem(openlist, { x = px, y = py, g = 0, h = tempH, f = 0 + tempH, par = 0 } )
While listk > -1
Local lowestF = openlist[listk].f
basis = listk
For Local k = listk To 0 Step -1
If openlist[k].f < lowestF lowestF = openlist[k].f basis = k EndIf Next closedk = closedk + 1 InsertItem(closedlist, openlist[basis], closedk) curbase = closedlist[closedk] Local rightOK = True Local leftOK = True Local downOK = True Local upOK = True If closedk > -1
For k = 0 To closedk
If closedlist[k].x = curbase.x + 1 And closedlist[k].y = curbase.y Then rightOK = False
If closedlist[k].x = curbase.x - 1 And closedlist[k].y = curbase.y Then leftOK = False
If closedlist[k].x = curbase.x And closedlist[k].y = curbase.y + 1 Then downOK = False
If closedlist[k].x = curbase.x And closedlist[k].y = curbase.y - 1 Then upOK = False
Next
EndIf
If curbase.x + 1 > xsize Then rightOK = False
If curbase.x - 1 < 0 Then leftOK = False If curbase.y + 1 > ysize Then downOK = False
If curbase.y - 1 < 0 Then upOK = False If curbase.x + 1 <= xsize And mapmat[curbase.y][curbase.x + 1] <> 0 Then rightOK = False
If curbase.x - 1 >= 0 And mapmat[curbase.y][curbase.x - 1] <> 0 Then leftOK = False
If curbase.y + 1 <= ysize And mapmat[curbase.y + 1][curbase.x] <> 0 Then downOK = False
If curbase.y - 1 >= 0 And mapmat[curbase.y - 1][curbase.x] <> 0 Then upOK = False
tempG = curbase.g + 1
For Local k = 1 To listk
If rightOK And openlist[k].x = curbase.x + 1 And openlist[k].y = curbase.y And openlist[k].g > tempG
tempH = Abs((curbase.x + 1) - tx) + Abs(curbase.y - ty)
InsertItem(openlist, {x = curbase.x + 1, y = curbase.y, g = tempG, h = tempH, f = tempG + tempH, par = closedk}, k)
rightOK = False
EndIf
If leftOK And openlist[k].x = curbase.x - 1 And openlist[k].y = curbase.y And openlist[k].g > tempG
tempH = Abs((curbase.x - 1) - tx) + Abs(curbase.y - ty)
InsertItem(openlist, {x = curbase.x - 1, y = curbase.y, g = tempG, h = tempH, f = tempG + tempH, par = closedk}, k)
leftOK = False
EndIf
If downOK And openlist[k].x = curbase.x And openlist[k].y = curbase.y + 1 And openlist[k].g > tempG
tempH = Abs(curbase.x - tx) + Abs((curbase.y + 1) - ty)
InsertItem(openlist, {x = curbase.x, y = curbase.y + 1, g = tempG, h = tempH, f = tempG + tempH, par = closedk}, k)
downOK = False
EndIf
If upOK And openlist[k].x = curbase.x And openlist[k].y = curbase.y - 1 And openlist[k].g > tempG
tempH = Abs(curbase.x - tx) + Abs((curbase.y - 1) - ty)
InsertItem(openlist, {x = curbase.x, y = curbase.y - 1, g = tempG, h = tempH, f = tempG + tempH, par = closedk}, k)
upOK = False
EndIf
Next
If rightOK
listk = listk + 1
tempH = Abs((curbase.x + 1) - tx) + Abs(curbase.y - ty)
InsertItem(openlist, {x = curbase.x + 1, y = curbase.y, g = tempG, h = tempH, f = tempG + tempH, par = closedk }, listk)
EndIf
If leftOK
listk = listk + 1
tempH = Abs((curbase.x - 1) - tx) + Abs(curbase.y - ty)
InsertItem(openlist, {x = curbase.x - 1, y = curbase.y, g = tempG, h = tempH, f = tempG + tempH, par = closedk }, listk)
EndIf
If downOK
listk = listk + 1
tempH = Abs(curbase.x - tx) + Abs((curbase.y + 1)- ty)
InsertItem(openlist, {x = curbase.x, y = curbase.y + 1, g = tempG, h = tempH, f = tempG + tempH, par = closedk }, listk)
EndIf
If upOK
listk = listk + 1
tempH = Abs(curbase.x - tx) + Abs((curbase.y - 1)- ty)
InsertItem(openlist, {x = curbase.x, y = curbase.y - 1, g = tempG, h = tempH, f = tempG + tempH, par = closedk }, listk)
EndIf
RemoveItem(openlist, basis)
listk = listk - 1
If closedlist[closedk].x = tx And closedlist[closedk].y = ty Then Return(closedlist)
Wend
Return(Nil)
EndFunction
Function CalcPath(closedlist)
If closedlist = Nil Then Return(Nil)
Local path = {}
Local pathIndex = {}
Local last = ListItems(closedlist) - 1
InsertItem(pathIndex, last, 0)
Local i = 0
While pathIndex > 0
i = i + 1
InsertItem(pathIndex, closedlist[pathIndex].par, i)
Wend
For Local n = ListItems(pathIndex) - 1 To 0 Step -1
InsertItem(path, { x = closedlist[pathIndex[n]].x, y = closedlist[pathIndex[n]].y })
Next
closedlist = Nil
Return(path)
EndFunction
map = {}
map[0] = { 0, 1, 0, 0, 0 }
map[1] = { 0, 1, 0, 0, 0 }
map[2] = { 0, 1, 0, 0, 0 }
map[3] = { 0, 1, 0, 1, 0 }
map[4] = { 0, 0, 0, 1, 0 }
moves = CalcMoves(map, 0, 0, 4, 4)
path = CalcPath(moves)
If path <> Nil
For i = 0 To ListItems(path) - 1
DebugPrint("move:", "(", path.x, ",", path.y, ")")
Next
Else
DebugPrint("Sorry, no path to target")
EndIf
La communauté Amiga est bien la meilleur, je demande un coup de main pour créé un code, et un amigaiste me file carrément le code source et qui fonctionne super bien en plus….
@Tarzin: plus qu’a l’adapter caillin Oh que oui on est tout petit, imagine, en 20 minutes… pfff… bon je suis dessus, je dois insérer un compteur de changement de direction car on a le droit qu’a 3 changement, il à mis un exe sur le forum d’holly, test le, sa claque….
@Crisot: Le jour ou j’arriverai à faire un pathfinding comme AOE2 les poules auront des dents
Tu pourrais l’adapter pour le C et comme tu t’y connais en 3D, l’adapter pour de la 3D justement… Comme sa tu nous fais un AOE4
humm.. mais il y a des l’indentation là-dedans!
Sur un autre fils, on regrette l’indentation obligatoire dans Python par-rapport à Lua.
Serait-ce un faux argument?!
15 sujets de 1 à 15 (sur un total de 19)
- 1
- 2
- Vous devez être connecté pour répondre à ce sujet.
