- Joined
- Jan 19, 2008
- Messages
- 69
I have a grid of cells (see attachment 1) and I need find the shortest path between any two of these cells.
So I tried to create something like a breath first search system. This is what my code looks like:
Creating the cells:
Breadth first search:
The result is not quite what I'm looking for (see attachment 2). I've been loosely following a tutorial on Red Blob Games: Introduction to A* and I'd like my search result to look like his (see attachment 3). Red circles in attachment 2 correspond to a down arrow in attachment 3, blue circle to an up arrow etc.
I can tell this happens because the order in which cells are queued is fixed (first north, then south, then east, then west). But I can't figure out how to get around this. Any ideas?
Thanks : )
So I tried to create something like a breath first search system. This is what my code looks like:
Creating the cells:
JASS:
scope GenerateDungeon initializer init
globals
integer DungeonRows = 15
integer DungeonColumns = 16
integer DungeonSize = DungeonRows * DungeonColumns
unit array DungeonCell
boolean array CellOnWBorder
boolean array CellOnEBorder
boolean array CellOnSBorder
boolean array CellOnNBorder
integer array BFSQueue
group BFSCellVisited = CreateGroup()
endglobals
private function Generate_Dungeon_Actions takes nothing returns boolean
local real x = GetUnitX(gg_unit_n000_0001)
local real y = GetUnitY(gg_unit_n000_0001)
local real x2
local real y2
local real d = 128.
local integer A
local integer B = 1
local integer i = 1
call RemoveUnit(gg_unit_n000_0001)
loop
set A = 1
loop
set x2 = x + d * A - d
set y2 = y + d * B - d
set DungeonCell[i] = CreateUnit(Player(PLAYER_NEUTRAL_PASSIVE), 'n000', x2, y2, 270)
if A == 1 then
set CellOnWBorder[i] = true
endif
if A == DungeonRows then
set CellOnEBorder[i] = true
endif
if B == 1 then
set CellOnSBorder[i] = true
endif
if B == DungeonColumns then
set CellOnNBorder[i] = true
endif
set i = i + 1
set A = A + 1
exitwhen A > DungeonRows
endloop
set B = B + 1
exitwhen B > DungeonColumns
endloop
return false
endfunction
//===========================================================================
private function init takes nothing returns nothing
local trigger t = CreateTrigger()
call TriggerRegisterTimerEventSingle(t, 0.00 )
call TriggerAddCondition(t, function Generate_Dungeon_Actions)
set t = null
endfunction
endscopeBreadth first search:
JASS:
scope BreadthFirstSearch initializer init
private function GetCellNeighbourN takes integer i returns integer
if CellOnNBorder[i] == true then
return 0
else
return i + DungeonRows
endif
endfunction
private function GetCellNeighbourS takes integer i returns integer
if CellOnSBorder[i] == true then
return 0
else
return i - DungeonRows
endif
endfunction
private function GetCellNeighbourE takes integer i returns integer
if CellOnEBorder[i] == true then
return 0
else
return i + 1
endif
endfunction
private function GetCellNeighbourW takes integer i returns integer
if CellOnWBorder[i] == true then
return 0
else
return i - 1
endif
endfunction
private function BreadthFirstSearch takes integer i returns nothing
local integer N
local integer S
local integer E
local integer W
local integer count = 1
local integer count2 = 1
loop
set N = GetCellNeighbourN(BFSQueue[count])
if N != 0 and IsUnitInGroup(DungeonCell[N], BFSCellVisited) == false then
set count2 = count2 + 1
set BFSQueue[count2] = N
call GroupAddUnitSimple(DungeonCell[N], BFSCellVisited)
call SetUnitColor(DungeonCell[N], PLAYER_COLOR_RED)
endif
set S = GetCellNeighbourS(BFSQueue[count])
if S != 0 and IsUnitInGroup(DungeonCell[S], BFSCellVisited) == false then
set count2 = count2 + 1
set BFSQueue[count2] = S
call GroupAddUnitSimple(DungeonCell[S], BFSCellVisited)
call SetUnitColor(DungeonCell[S], PLAYER_COLOR_BLUE)
endif
set E = GetCellNeighbourE(BFSQueue[count])
if E != 0 and IsUnitInGroup(DungeonCell[E], BFSCellVisited) == false then
set count2 = count2 + 1
set BFSQueue[count2] = E
call GroupAddUnitSimple(DungeonCell[E], BFSCellVisited)
call SetUnitColor(DungeonCell[E], PLAYER_COLOR_YELLOW)
endif
set W = GetCellNeighbourW(BFSQueue[count])
if W != 0 and IsUnitInGroup(DungeonCell[W], BFSCellVisited) == false then
set count2 = count2 + 1
set BFSQueue[count2] = W
call GroupAddUnitSimple(DungeonCell[W], BFSCellVisited)
call SetUnitColor(DungeonCell[W], PLAYER_COLOR_PURPLE)
endif
set count = count + 1
exitwhen CountUnitsInGroup(BFSCellVisited) == DungeonSize
endloop
endfunction
private function StartSearch takes nothing returns boolean
local unit u = GetTriggerUnit()
local integer i = 1
loop
if DungeonCell[i] == u then
set BFSQueue[1] = i
call GroupAddUnitSimple(DungeonCell[i], BFSCellVisited)
call BreadthFirstSearch(1)
call SetUnitColor(u, PLAYER_COLOR_GREEN)
endif
exitwhen i == DungeonSize or DungeonCell[i] == u
set i = i + 1
endloop
set u = null
return false
endfunction
//===========================================================================
private function init takes nothing returns nothing
local trigger t = CreateTrigger()
call TriggerRegisterPlayerSelectionEventBJ(t, Player(0), true)
call TriggerAddCondition(t, function StartSearch)
set t = null
endfunction
endscopeThe result is not quite what I'm looking for (see attachment 2). I've been loosely following a tutorial on Red Blob Games: Introduction to A* and I'd like my search result to look like his (see attachment 3). Red circles in attachment 2 correspond to a down arrow in attachment 3, blue circle to an up arrow etc.
I can tell this happens because the order in which cells are queued is fixed (first north, then south, then east, then west). But I can't figure out how to get around this. Any ideas?
Thanks : )
Last edited:
