Quenty
|
  |
| Joined: 03 Sep 2009 |
| Total Posts: 9316 |
|
|
| 24 May 2012 07:40 PM |
What does it appear that I am doing wrong? My datastructures are kind of random, and I need advice.
This is an A* pathfinder. I've worked on it for about 8 hours, so I kind of think... you know, I should ask here.
I'm following the procedure from Amit's A* stuff. which is here:
------------------------------------------------------ OPEN = priority queue containing START CLOSED = empty set while lowest rank in OPEN is not the GOAL: current = remove lowest rank item from OPEN add current to CLOSED for neighbors of current: cost = g(current) + movementcost(current, neighbor) if neighbor in OPEN and cost less than g(neighbor): remove neighbor from OPEN, because new path is better if neighbor in CLOSED and cost less than g(neighbor): ** remove neighbor from CLOSED if neighbor not in OPEN and neighbor not in CLOSED: set g(neighbor) to cost add neighbor to OPEN set priority queue rank to g(neighbor) + h(neighbor) set neighbor's parent to current
reconstruct reverse path from goal to start by following parent pointers ------------------------------------------------------ Here is my map generating function: Captures stuff from terrain.
function GenerateMap(TerrainY) -- TerrainY is the height to scan it for. Scanning, not really generating. if not _G.Map then print("Generating Map") local TimeTook = tick() for X=LowerX, UpperX do Map[X] = {} local Ref = Map[X] for Y=LowerY, UpperY do local Material--[[, Type, Orientation--]] = TerrainGetCell(Terrain, X,TerrainY,Y) Ref[Y] = {} Ref[Y].Transversable = (Material == Enum.CellMaterial.Empty) --Trans --Empty or not. :D Ref[Y].Neighbors = { {X = X+1; Y = Y+1}; {X = X; Y = Y+1}; {X = X-1; Y = Y+1}; {X = X-1; Y = Y}; {X = X+1; Y = Y}; {X = X-1; Y = Y-1}; {X = X; Y = Y-1}; {X = X+1; Y = Y-1}; } end if X % 10 == 0 then --Don't lag out the server at the beginning... print("Wait For "..X) wait() end end _G.Map = Map print("It took: "..tick()-TimeTook.." seconds to complete the terrain capture") else print("Map has already been generated, getting it from _G.Map") Map = _G.Map end end
Actual Code: ------------------------------------------------------ If you're an A* person, can you just kind of look over this, and tell me if anything looks wrong... I mean, This is annoying. It goes towards the target, get's all these 'Red' bricks, which aren't suppose to happen (Errors), and then it somehow runs out of items in the open set...
Anyway, I know there's a logical problem here. SOMEONE FIND IT pl0x?
All, I really really need advice on datastructures.
local function AStar(Start, Goal) print("AStar start")
Start["GScore"] = 0 -- Distance from start. Start["HScore"] = Heuristic(Start,Goal) -- Estimated Distance from Goal Start["FScore"] = Start.GScore + Start.HScore -- The Final Score
local OpenSet = {Start} -- The OpenSet is the set of nodes that need to be check. In each repetition, it pulls out the smallest 'Scoring' one, and checks it. local ClosedSet = {} -- The ClosedSet is the set of nodes that have already been visited
local Continue = true -- Until the Goal is found, continue will be true. local LowestNode, IndexVal local Reps = 0
local function GetLowestRankInOpen() local LowestNode, IndexVal; local CurrentNodeFScore = math.huge print("OpenSet has :"..#OpenSet.." options") for Index, Node in pairs(OpenSet) do if Node.FScore <= CurrentNodeFScore then CurrentNodeFScore = Node.FScore LowestNode = Node IndexVal = Index; end end return LowestNode, IndexVal; end
local function NodeIsTransversable(NodeX, NodeY) local MapX = Map[NodeX] -- Node out of bounds? if not MapX then print("Node out of bounds") return false end local MapXY = MapX[NodeY] -- Node out of bounds? if not MapXY then print("Node out of bounds") return false end return MapXY.Transversable end
function NodeIsInOpenSet(NodeX, NodeY) for Index, Node in pairs(OpenSet) do if Node.X == NodeX and Node.Y == NodeY then return true, Node, Index end end return false end
function NodeIsInClosedSet(NodeX, NodeY) for Index, Node in pairs(ClosedSet) do if Node.X == NodeX and Node.Y == NodeY then return true, Node, Index end end return false end
local function ReconstructPath(Node, Tab) Tab = Tab or {} table.insert(Tab, Node) return Node.Source and ReconstructPath(Node.Source, Tab) or Tab; end
local function Check(Num) for _, Node in pairs(OpenSet) do if Node.FScore < Num then print("failed @ "..Node.FScore) end end end
while #OpenSet > 0 do Reps = Reps + 1 print("Loop #: "..Reps) LowestNode, IndexVal = GetLowestRankInOpen() print(LowestNode and "Lowest node is there" or "Lowest node is not there") local LowestNodeX = LowestNode.X local LowestNodeY = LowestNode.Y print("FScore: "..LowestNode.FScore) Check(LowestNode.FScore) wait(0.1) if (LowestNodeX ~= Goal.X) and (LowestNodeY ~= Goal.Y) then ClosedSet[#ClosedSet+1] = LowestNode OpenSet[IndexVal] = nil if OpenSet[IndexVal] then print("Hack") end
RenderNiceBrick(LowestNodeX, LowestNodeY, BrickColor.new("Mid gray"))
for _, NeighborNode in pairs(Map[LowestNodeX][LowestNodeY].Neighbors) do local NeighborNodeX = NeighborNode.X -- Speed things up local NeighborNodeY = NeighborNode.Y if NodeIsTransversable(NeighborNodeX, NeighborNodeY) then local NeighborGScore = LowestNode.GScore + Heuristic(LowestNode, NeighborNode) local NeighborHScore = Heuristic(NeighborNode, Goal) local NeighborFScore = NeighborHScore + NeighborGScore local NodeIsInOpen, OpenNode, OpenIndex = NodeIsInOpenSet(NeighborNodeX, NeighborNodeY) local NodeIsInClosed, ClosedNode, ClosedIndex = NodeIsInClosedSet(NeighborNodeX, NeighborNodeY)
print("Node["..NeighborNodeX.."]["..NeighborNodeY.."]") print(" Node is in Open: ",NodeIsInOpen) print(" Node is in Closed: ",NodeIsInClosed) print(" Node FScore: ", NeighborFScore)
if NodeIsInOpen and NeighborGScore < OpenNode.GScore then RenderNiceBrick(NeighborNodeX,NeighborNodeY, BrickColor.new("Bright orange")) --print(" Old position is better") OpenSet[OpenIndex] = nil --NodeIsInOpen = false end
if NodeIsInClosed and NeighborHScore < ClosedNode.GScore then RenderNiceBrick(NeighborNodeX,NeighborNodeY, BrickColor.new("Bright red")) print(" Heuristic Error") ClosedSet[ClosedIndex] = nil NodeIsInClosed = false end
if not NodeIsInClosed and not NodeIsInOpen then print(" Node identified") RenderNiceBrick(NeighborNodeX,NeighborNodeY, BrickColor.new("Bright blue")) local NewNode = {} NewNode.X = NeighborNodeX NewNode.Y = NeighborNodeY NewNode["GScore"] = NeighborGScore NewNode["HScore"] = NeighborHScore NewNode["FScore"] = NeighborFScore NewNode.Source = LowestNode OpenSet[#OpenSet+1] = NewNode end else RenderNiceBrick(NeighborNodeX,NeighborNodeY, BrickColor.new("Hot pink")) print("Can't walk on dat") end end else RenderNiceBrick(LowestNode.X,LowestNode.Y, BrickColor.new("Bright yellow")) Continue = false print("Found goal") end end
print("Done with A*") return true, ReconstructPath(LowestNode, {}); end |
|
|
| Report Abuse |
|
|
Tenal
|
  |
| Joined: 15 May 2011 |
| Total Posts: 18684 |
|
| |
|
Quenty
|
  |
| Joined: 03 Sep 2009 |
| Total Posts: 9316 |
|
| |
|
Quenty
|
  |
| Joined: 03 Sep 2009 |
| Total Posts: 9316 |
|
|
| 24 May 2012 07:46 PM |
I should go use the inefficient version I had...
I should make Julien mad.
Ololol.
Nah. Someone please please help. D: |
|
|
| Report Abuse |
|
|
Aerideyn
|
  |
| Joined: 16 Jan 2010 |
| Total Posts: 1882 |
|
|
| 24 May 2012 08:13 PM |
It has been too long.. i remember i managed to get one working about 6 months ago.. i probably have the script around here somewhere though from memory it worked on a 1stud voxel grid (floor the position of the player for start node etc) and didnt support multiple levels.. but if you want it i can probably upload the script.
|
|
|
| Report Abuse |
|
|
Quenty
|
  |
| Joined: 03 Sep 2009 |
| Total Posts: 9316 |
|
|
| 24 May 2012 08:48 PM |
I have a working version.
I want to know what's wrong with this one I wrote now...
See any design flaws? |
|
|
| Report Abuse |
|
|
ENET
|
  |
| Joined: 01 Jan 2010 |
| Total Posts: 4820 |
|
| |
|
MajorTyco
|
  |
| Joined: 09 Apr 2010 |
| Total Posts: 1989 |
|
|
| 24 May 2012 10:45 PM |
I agree. That code makes me..*hesitate, pose like that guy in the fiberOne commerical* sad.
Error in function Gag, line 1337: Too Lazy to Write Variable "siggy" |
|
|
| Report Abuse |
|
|
NXTBoy
|
  |
| Joined: 25 Aug 2008 |
| Total Posts: 4533 |
|
|
| 25 May 2012 03:26 AM |
For a start, I'd be tempted to use the nodes as keys rather than values in open and closed set. Possibly something like this:
openset[node] = { g = ..., h = ..., f = ..., cameFrom = anotherNode -- used to build up the path backwards }
This is better than attaching properties to the nodes themselves, because you can reuse the nodes when you run the algorithm again. |
|
|
| Report Abuse |
|
|
NXTBoy
|
  |
| Joined: 25 Aug 2008 |
| Total Posts: 4533 |
|
|
| 25 May 2012 03:57 AM |
| Also, a quick code style note - it's bad practice to use tabs for alignment (equals signs, comments, etc), since they only align if the tab size is the same as the one you were using. Tabs for indentation, spaces for alignment. |
|
|
| Report Abuse |
|
|
Quenty
|
  |
| Joined: 03 Sep 2009 |
| Total Posts: 9316 |
|
|
| 25 May 2012 02:07 PM |
I tried to use Nodes as keys, but that means I had to use to do some really hacky stuff or something..
As for alignment... Yeah, good idea. |
|
|
| Report Abuse |
|
|
|
| 25 May 2012 03:32 PM |
this might be wrong but surely it's a bit of a stupid idea to cram hundreds of functions into a function
it'd need to redo them into the memory every time it ran and since it's garbage collected not manual and it obviously isn't nice on the processor to keep defining functions over and over, you should just put them in a table or something if you're going to be using them often |
|
|
| Report Abuse |
|
|
Quenty
|
  |
| Joined: 03 Sep 2009 |
| Total Posts: 9316 |
|
|
| 25 May 2012 03:35 PM |
Hmm.. yeh.
I know I have a really big logical problem in that mess.... Like a REALLY big one. I just can't find it.
But yes. Tell me all my bad scripting practices... I know I have a lot of them. |
|
|
| Report Abuse |
|
|
NXTBoy
|
  |
| Joined: 25 Aug 2008 |
| Total Posts: 4533 |
|
|
| 25 May 2012 03:37 PM |
They have closures on the surrounding variables - that's why they have to be there. The only solution would be object-orientation and metatables, which would probably be overkill.
Constructing a handful of functions costs nothing compared to running an A* algorithm. |
|
|
| Report Abuse |
|
|
Quenty
|
  |
| Joined: 03 Sep 2009 |
| Total Posts: 9316 |
|
|
| 25 May 2012 03:45 PM |
@NXTBoy... No. Easy solution:
function Whatever(ATable, restOfarguments) -- Do the stuff... end
|
|
|
| Report Abuse |
|
|
NXTBoy
|
  |
| Joined: 25 Aug 2008 |
| Total Posts: 4533 |
|
|
| 25 May 2012 03:49 PM |
| Bleh. Looks messy. I prefer your closure way of doing things. |
|
|
| Report Abuse |
|
|
Quenty
|
  |
| Joined: 03 Sep 2009 |
| Total Posts: 9316 |
|
|
| 26 May 2012 10:17 AM |
True. True.
Still, any way works fine. Environments are tricky. |
|
|
| Report Abuse |
|
|
2013henry
|
  |
| Joined: 09 Apr 2013 |
| Total Posts: 39768 |
|
| |
|
|
| 13 Apr 2016 12:42 AM |
2013henry you're stupid. You bumped a 4 year old thread in case you didn't know. |
|
|
| Report Abuse |
|
|
| |
|
| |
|
Exgle
|
  |
| Joined: 03 Jun 2011 |
| Total Posts: 132 |
|
| |
|
| |
|