Hello,
Ayant fini de gérer le déplacement dans Dofus 1.29 je souhaitais partager. Je n'ai pas eu le temps de le tester au max, ilse peut donc qu'il y ait une coquille ou deux. N'hésitez pas a me signaler si votre déplacement ne fonctionne pas en me donnant ( la map id, cellule de départ, cellule d'arrivée ).
Ici on partira des maps déjà décodé. Je n'ai quasiment pas mis le nez dans le client, mon but n'étant pas de recopier le code client.
Quand on reçoit une map ( GDM ) comme info on a donc x cellules et une longueur + largeur.
Les maps étant iso, une ligne sur deux comportera soit Longueur cases soit Longueur -1 cases ( très important ). On nommera cases paire celles avec "Longueur" cases et impaires celles avec "longueur -1" cases (Pour trouver simplement il suffit de regarder si Y est paire ou impaire)
Pour cette explication j'ai choisi cette carte ( 2;-18 ).
Voila deux modélisation de débug. Une iso et une ou j'ai fais une matrice.

![img]()
Les cases bleues cyan sont des cases non déplaçables.
Les violettes des soleils
Les bleues foncées des cases cliquables ( maisons, ressources etc ).
J'ai inséré dans chaque cases la valeure de sa cell_id.
Pour arriver a mon but j'utilise l'algo aStar qui a besoin d'un tableau a deux dimensions et d'une case de départ et une case d'arrivée, logique. Ces coordonnées seront carthésiennes ( x,y).
On se rends compte qu'il va falloir deux fonctions :
Passer de x,y a la cell id et inverse.
Elles sont a la fin de ce post sous les noms : from_cell_id_to_x_y_pos et from_pos_x_y_to_cell_id
Ensuite l’algorithme astar a besoin d'un tableau a deux dimensions avec le même nombre d'élément dans chaque lignes. J'ai donc ajouté une case , une ligne sur deux pour former un tableau. Je l'ai transformé en tableau Numpy ( populaire et performant en python). Il faudra échanger les axes car numpy fais y, x et non x, y ( fonction " from_array_map_to_numpy" )
De plus ce tableau doit être composé de 0 et de 1. A vous de voir ce que vous considérez comme des cellules déplaçables ou non. Les bleux cyan étant bien évidemment non déplaçables, cela dépendra de vous pour les montres / les soleils etc.
Voici la matrice que j'obtient sur cette carte ( J'ai mis les soleils, les bleus foncés et les cyans en non déplaçables ).
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1]
[1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1]
[0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1]
[1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1]
[0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1]
[1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1]
[1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1]
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
[0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1]
[1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
Parfait plus qu'a lancer Astar ... ou pas :)
Le problème est que la map de Dofus est isométrique. La notre est un tableau. Ainsi aucun problème pour astar de faire ce chemin :
cellules : 20-21-36-52
En regardant la map matrice cela semble possible mais pas sur la map iso ( 36 a 52 est impossible )
Pour ceux qui ont lu le fonctionnement de Astar -> On va brider les cases que l'algo regarde pour continuer son chemin suivant si on est sur une ligne paire ou non.
Voici la fonction astar d'un algo trouvé en ligne que j'ai adapté pour les maps iso.
import numpy as np
import heapq
import matplotlib.pyplot as plt
from matplotlib.pyplot import figure
##############################################################################
# heuristic function for path scoring
##############################################################################
def heuristic(a, b):
return np.sqrt((b[0] - a[0]) ** 2 + (b[1] - a[1]) ** 2)
##############################################################################
# path finding function
##############################################################################
def astar(array, start, goal):
# original one
neighbors = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1),(0 ,2), (0, -2)]
# based on y value
odd_neighbors = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1),(0 ,2), (0, -2)]
pair_neighbors = [(0, 1), (0, -1), (1, 0), (-1, 0), (-1, 1), (-1, -1),(0 ,2), (0, -2)]
close_set = set()
came_from = {}
gscore = {start: 0}
fscore = {start: heuristic(start, goal)}
oheap = []
heapq.heappush(oheap, (fscore[start], start))
while oheap:
current = heapq.heappop(oheap)[1]
if current == goal:
data = []
while current in came_from:
data.append(current)
current = came_from[current]
data.append(start)
data = data[::-1]
return data
close_set.add(current)
if current[1] % 2 == 0:
pimp_neighbors = pair_neighbors
else:
pimp_neighbors = odd_neighbors
for i, j in pimp_neighbors:
neighbor = current[0] + i, current[1] + j
multiply = 1
# if current_line_simetry == 'pair':
if abs(i) == 1 and j == 0:
multiply = 1.2
if abs(i + j) == 2:
multiply = 0.7
tentative_g_score = gscore[current] + heuristic(current, neighbor) * multiply
try:
if 0 <= neighbor[0] < array.shape[0]:
if 0 <= neighbor[1] < array.shape[1]:
if array[neighbor[0]][neighbor[1]] == 1:
continue
else:
# array bound y walls
continue
else:
# array bound x walls
continue
except:
continue
if neighbor in close_set and tentative_g_score >= gscore.get(neighbor, 0):
continue
if tentative_g_score < gscore.get(neighbor, 0) or neighbor not in [i[1] for i in oheap]:
came_from[neighbor] = current
gscore[neighbor] = tentative_g_score
fscore[neighbor] = tentative_g_score + heuristic(neighbor, goal)
heapq.heappush(oheap, (fscore[neighbor], neighbor))
return False
J'ai modifié la liste des "neighbor". J'ai rajouté le déplacement de deux cases verticale ( 0,2 ) et (0,-2).
Pour les déplacements des lignes paire ou impaire voici une explication.
Si la cell id : 38 est notre point de départ
Nous pouvons aller notamment sur les cases : 52 et 53. Sur notre matrice cela correspond a [1, -1] et [1, 0]
Si la cell id : 53 est notre point de départ
Nous pouvons aller notamment sur les cases : 67 et 68. Sur notre matrice cela correspond a [0, 1] et [1, 1]
Suivant que l'on soit sur une ligne paire ou impaire il ne nous faut pas regarder avec le même "différentiel".
Les listes "odd_neighbors" et "pair_neighbors" sont des adaptations de "neighbors" en prenant en compte cette idée de ligne paire / impaire.
A noter que j'ai rajouté des multiplicateurs de score heuristique pour que les déplacements en diagonales soit privilégiés ( en mettant un multiplicateur inférieur a 1 pour les déplacements horizontal ) et ceux de deux cases vers le bas ( exemple : cellule 52 a 80 ).
Astar nous renvois donc un path réalisable pour dofus, Youpie :D
Comment l'envoyer a dofus ?
Pour cette partie merci a ce tuto : https://cadernis.com/d/1767-deplacement-dofus-1-29 ( post 3 )
Il nous faut donc encoder sur 3 charactéres représentant des lignes droites.
La encore les lignes paires impaires vont nous embêter. La fonction qui parse le path est donc : "convert_astar_path_to_dofus_path" qui s'appuiera sur la fonction "find_direction".
Et voila vous pouvez a prioris vous déplacer façilement dans Dofus maintenant. Je rajouterais l'implémentation du temps de déplacements plus tard.
import numpy
import app.tools.crypt as Crypt
def from_array_map_to_numpy(map_array, width_):
new_map = numpy.empty((0, width_))
for line in map_array:
new_map = numpy.append(new_map, [line], axis=0)
# Swap axes else y will become y >.>!
new_map = numpy.swapaxes(new_map, 0, 1)
return new_map
def find_direction(start_cell, end_cell):
dirs = {'e': 0, 'se' : 1, 's' : 2, 'sw' : 3, 'w' : 4, 'nw' : '5', 'n' : 6, 'ne' : 7 }
t_ = ''
is_start_cell_on_pair_line = True if ( start_cell[1] % 2 == 0 ) else False
is_end_cell_on_pair_line = True if (end_cell[1] % 2 == 0) else False
# North or south
if start_cell[1] - end_cell [1] > 0:
t_ += 'n'
elif start_cell[1] - end_cell[1] < 0:
t_ += 's'
# if t_ has not N or S , it means it's only vertical deplacement
if t_ == '':
if start_cell[0] - end_cell[0] < 0:
t_ += 'e'
elif start_cell[0] - end_cell[0] > 0:
t_ += 'w'
else:
# care the user is not trying to go 2 cases down and then we don't care about x.
if is_start_cell_on_pair_line and is_end_cell_on_pair_line is False:
if start_cell[0] - end_cell[0] == 0:
t_ += 'e'
elif start_cell[0] - end_cell[0] > 0 :
t_ += 'w'
elif start_cell[0] - end_cell[0] < 0:
print('ERROR THIS SHOULNT BE ALLOWED')
elif is_start_cell_on_pair_line is False and is_end_cell_on_pair_line is True:
if start_cell[0] - end_cell[0] == 0:
t_ += 'w'
elif start_cell[0] - end_cell[0] > 0 :
print('ERROR THIS SHOULNT BE ALLOWED')
elif start_cell[0] - end_cell[0] < 0:
t_ += 'e'
value = dirs[t_]
return value
def from_cell_id_to_x_y_pos(cell_id, width):
pos_y = ( cell_id // (((width )*2)-1 ))*2
if ( cell_id % (((width )*2)-1 )) >= width:
pos_y += 1
if cell_id > ( width -1 ) *2:
add = 1
pos_x = (cell_id + (pos_y // 2)) % (width ) + add
else:
pos_x = cell_id % (width) + 1
return pos_x - 1, pos_y
def from_pos_x_y_to_cell_id(x, y, map_width):
sous = (y // 2)
cell_id = (y * map_width) + (x ) - sous
return cell_id
def convert_astar_path_to_dofus_path(path, map_width):
le_path = ''
last_dir = None
last_cell = None
for i in range(1, len(path)):
last_cell = path[i-1]
cell = path
dir = find_direction(last_cell, cell)
if i == 1:
last_dir = dir
if dir != last_dir:
cell_id = from_pos_x_y_to_cell_id(last_cell[0], last_cell[1], map_width)
le_path += Crypt.encrypt_path_step(cell_id, last_dir)
last_dir = dir
# add the end
last_cell = path[-1]
cell_id = from_pos_x_y_to_cell_id(last_cell[0], last_cell[1], map_width)
le_path += Crypt.encrypt_path_step(cell_id, last_dir)
return le_path, 0