Posté le: 15/03/16 20:33 Sujet du message: Générateur de labyrinthe
Je suis entrain en construire un générateur de Donjon. La première étape consiste à créer un générateur de labyrinthe simple. Mon code semble fonctionné pour des petites tailles de labyrinthe mais dès que je rentre des valeurs un peu grande (mais théoriquement possible) le script ne s'accomplit jamais (pas de lag, juste rien). C'est comme si il s'arrête en plein milieu de processus (littéralement en fait si on regarde le nombre de cases visités ou le nombre de cases générés si la création du donjon est accomplis). Parfois enlever des lignes call BJ DebugMsg m'a permis de faire pousser plus loin la génération du labyrinthe de quelques cellules. Optimiser la gestion de l'aléatoire dans le choix des directions m'a aussi permis d'augmenter la taille des labyrinthe possible mais je reste très loin du maximum théorique.
j'aimerais savoir si vous avez une idée de la source de la limitation et comment la contourner.
Voici le script. Il faut encore que je travaille pas mal d'aspects mais il fonctionne.
//===========================================================================
// DIRECTION
//===========================================================================
private struct Direction extends array
readonly static thistype North = 0
readonly static thistype South = 2
readonly static thistype East = 1
readonly static thistype West = 3
endstruct
private struct DirectionPicker
private Direction array dirPicked[4]
private integer count=3
method getNextDirection takes nothing returns Direction
local Direction d
local integer i
local real r
debug if not hasNextDirection() then
debug call BJDebugMsg("No more direction available")
debug endif
set r=GetRandomReal(0,1)
for i=0 to this.count
if i/(this.count+1)<r and r<(i+1)/(this.count+1) then
set d=dirPicked[i]
set dirPicked[i]=dirPicked[this.count]
break
endif
endfor
set this.count=this.count-1
return d
endmethod
static method create takes nothing returns thistype
local thistype this = thistype.allocate()
local integer i
local integer n
set n=GetRandomInt(0,3)
for i=0 to 3
set this.dirPicked[i]= (n+i)-((n+i)/4)*4//Modulo
endfor
method generate takes real x1, real y1 returns nothing
local real x = x1-128
local real y = y1+128
local integer i=0
local integer j=0
for i=0 to 2
for j=0 to 2
//To reduce
if i==1 and j==0 and this.NorthSide==SideType.Wall then
call CreateDestructable(SideType.Wall_Id,x+i*128,y-128*j,270,1,-1)
elseif i==1 and j==2 and this.SouthSide==SideType.Wall then
call CreateDestructable(SideType.Wall_Id,x+i*128,y-128*j,270,1,-1)
elseif i==0 and j==1 and this.WestSide==SideType.Wall then
call CreateDestructable(SideType.Wall_Id,x+i*128,y-128*j,270,1,-1)
elseif i==2 and j==1 and this.EastSide==SideType.Wall then
call CreateDestructable(SideType.Wall_Id,x+i*128,y-128*j,270,1,-1)
elseif i!=1 and j!=1 then
call CreateDestructable(SideType.Wall_Id,x+i*128,y-128*j,270,1,-1)
elseif i==1 and j==1 then
call CreateUnit(Player(0),'hpea',x+i*128,y-128*j,270)
endif
debug private function IsOutOfBounds takes integer r, integer c returns boolean
debug if (c < 0) and (c >= Width-1) and (r < 0) and (r >= Height-1) then
debug call BJDebugMsg("DG : Given coordinates are OOB")
debug return true
debug endif
debug return false
debug endfunction
private function HasAdjacentCellInDirection takes integer r, integer c, Direction d returns boolean
// Check that the location falls within the bounds of the map
debug if IsOutOfBounds(r,c) then
debug return false
debug endif
// Check if there is an adjacent cell in the direction
if d==Direction.North then
return r>0
elseif d==Direction.East then
return c<Width-1
elseif d==Direction.South then
return r<Height-1
elseif d==Direction.West then
return c>0
endif
return false
endfunction
private function IsAdjacentCellInDirectionVisited takes integer r, integer c, Direction d returns boolean
debug if not HasAdjacentCellInDirection(r,c,d) then
debug call BJDebugMsg("DG : No adjacent cell exist for the coordinates and direction provided")
debug endif
if d==Direction.North then
return cell[r-1][c].visited
elseif d==Direction.East then
return cell[r][c+1].visited
elseif d==Direction.South then
return cell[r+1][c].visited
elseif d==Direction.West then
return cell[r][c-1].visited
endif
return true
endfunction
private function GetTargetLoc takes integer r, integer c, Direction d returns nothing
debug if not HasAdjacentCellInDirection(r,c,d) then
debug call BJDebugMsg("DG : No adjacent cell exists for the coordinates and direction provided")
debug endif
if d==Direction.North then
set R = r-1
elseif d==Direction.East then
set C=c+1
elseif d==Direction.South then
set R=r+1
elseif d==Direction.West then
set C=c-1
endif
endfunction
private function CreateCorridor takes integer r, integer c, Direction d returns nothing
debug if not HasAdjacentCellInDirection(r,c,d) then
debug call BJDebugMsg("DG : No adjacent cell exist for the coordinates and direction provided")
debug endif
if d==Direction.North then
set cell[r][c].NorthSide=SideType.Empty
set cell[r-1][c].SouthSide=SideType.Empty
elseif d==Direction.East then
set cell[r][c].EastSide=SideType.Empty
set cell[r][c+1].WestSide=SideType.Empty
elseif d==Direction.South then
set cell[r][c].SouthSide=SideType.Empty
set cell[r+1][c].NorthSide=SideType.Empty
elseif d==Direction.West then
set cell[r][c].WestSide=SideType.Empty
set cell[r][c-1].EastSide=SideType.Empty
endif
call GetTargetLoc(r,c,d)//Change R and C according to the direciton
endfunction
private function SetCellPermaVisited takes integer r, integer c returns boolean
debug if IsOutOfBounds(r,c) then
debug return false
debug endif
debug if cell[r][c].visited and not cell[r][c].permaVisited then
set cell[r][c].permaVisited=true
return true
debug endif
debug return false
endfunction
private function SetCellVisited takes integer r, integer c returns boolean
debug if IsOutOfBounds(r,c) then
debug return false
debug endif
debug if not cell[r][c].visited then
set cell[r][c].visited=true
set VisitedCellsCount=VisitedCellsCount+1
set VisitedCells_R[VisitedCellsCount]=r
set VisitedCells_C[VisitedCellsCount]=c
return true
debug endif
debug return false
endfunction
private function GetRandomVisitedCell takes nothing returns nothing
local integer i = GetRandomInt(0,VisitedCellsCount)
debug if VisitedCellsCount==0 then
debug call BJDebugMsg("DG : There are no visited cell to return")
debug endif
while cell[VisitedCells_R[i]][VisitedCells_C[i]].permaVisited
set i=GetRandomInt(0, VisitedCellsCount)
endwhile
set R = VisitedCells_R[i]
set C = VisitedCells_C[i]
endfunction
private function InitAllCellsUnvisited takes nothing returns nothing
local integer r
local integer c
for c=0 to Width-1
for r=0 to Height-1
set cell[r][c]= Cell.create()
endfor
endfor
endfunction
//===========================================================================
// PUBLIC FUNCTIONS
//===========================================================================
public function Generate takes real x, real y returns nothing
local integer r
local integer c
for c=0 to Width-1
for r=0 to Height-1
call cell[r][c].generate(x+c*Cell.Size,y-r*Cell.Size)
endfor
endfor
endfunction
public function Create takes integer height, integer width returns nothing
local DirectionPicker dirpick
local Direction dir
set Height=height
set Width=width
call InitAllCellsUnvisited()//Mark all cells as unvisited
set R=GetRandomInt(0,Height-1)
set C=GetRandomInt(0,Width-1)
call SetCellVisited(R,C)//First Cell
while VisitedCellsCount != (Height)*(Width)//Out when all cells have been visited
debug call BJDebugMsg(I2S(VisitedCellsCount))
set dirpick = DirectionPicker.create()
set dir = dirpick.getNextDirection()
while not(HasAdjacentCellInDirection(R,C,dir)) or IsAdjacentCellInDirectionVisited(R,C,dir)//find a direction that works
if dirpick.hasNextDirection() then
set dir=dirpick.getNextDirection()
else
//Need to choose new current coordinates from previously visited locations
call SetCellPermaVisited(R,C)//we don't need this cell anymore
call GetRandomVisitedCell()
call dirpick.destroy()
set dirpick = DirectionPicker.create()
set dir=dirpick.getNextDirection()
endif
endwhile
call dirpick.destroy()
call CreateCorridor(R,C,dir)//Will provide R C to the cell where the corridor ends
call SetCellVisited(R,C)
endwhile
endfunction
Inscrit le: 21 Fév 2010 Messages: 1785 Sujets: 22 Spécialité en worldedit: La modestie Médailles: 1 (En savoir plus...)
Posté le: 15/03/16 21:29 Sujet du message:
Le jass ne permet pas d’exécuter un code trop long dans un seul thread. Si tu fais une boucle infinie dans un thread, elle se terminera automatiquement au bout d'un certain nombre d'étapes (je crois que TB avait fait quelques tests pour savoir combien d'instructions étaient possibles, et de quoi la limite dépendait).
Donc il faut t'arranger pour que, dans la boucle de ta fonction "Create" (la 1ère boucle, ça suffira si j'ai bien compris ton code), tu ouvres un nouveau thread à chaque exécution du bloc de code.
Un truc du genre :
Secret:
Jass:
function CreateLoop takes nothing returns nothing
local DirectionPicker dirpick
local Direction dir
debug call BJDebugMsg(I2S(VisitedCellsCount))
set dirpick = DirectionPicker.create()
set dir = dirpick.getNextDirection()
while not(HasAdjacentCellInDirection(R,C,dir)) or IsAdjacentCellInDirectionVisited(R,C,dir)//find a direction that works
if dirpick.hasNextDirection() then
set dir=dirpick.getNextDirection()
else
call SetCellPermaVisited(R,C)//we don't need this cell anymore
call GetRandomVisitedCell()
call dirpick.destroy()
set dirpick = DirectionPicker.create()
set dir=dirpick.getNextDirection()
endif
endwhile
call dirpick.destroy()
call CreateCorridor(R,C,dir)//Will provide R C to the cell where the corridor ends
call SetCellVisited(R,C)
endfunction
public function Create takes integer height, integer width returns nothing
set Height=height
set Width=width
call InitAllCellsUnvisited()//Mark all cells as unvisited
set R=GetRandomInt(0,Height-1)
set C=GetRandomInt(0,Width-1)
call SetCellVisited(R,C)//First Cell
while VisitedCellsCount != (Height)*(Width)//Out when all cells have been visited
call ExecuteFunc("CreateLoop")
// ou encore CreateLoop.execute()
// il me semble que c'est ça en vJass pour créer un trigger et utiliser "TriggerExecute" automatiquement
endwhile
endfunction
J'ai appliqué ce que tu m'as dis Tirlititi et ca marche ! Il faudra que je fasse de même pour la génération (création du donjon sur le terrain) j'imagine, cela ne devrait pas poser de problèmes maintenant. _________________
Pas benchmarké, mais Forforce est censé être le moyen le plus efficace pour s'affranchir du limit op.
Si tu as des questions je trainerais dans le coin. _________________
Super! Merci d'avoir pris le temps de faire cette ressource qui me sera fort utile pour ce script.
C'est assez simple donc je pese avoir compris complètement comment ca marche. _________________
Vous ne pouvez pas poster de nouveaux sujets dans ce forum Vous ne pouvez pas répondre aux sujets dans ce forum Vous ne pouvez pas éditer vos messages dans ce forum Vous ne pouvez pas supprimer vos messages dans ce forum Vous ne pouvez pas voter dans les sondages de ce forum