Quenty
|
  |
| Joined: 03 Sep 2009 |
| Total Posts: 9316 |
|
|
| 24 May 2012 02:47 PM |
I have an A* thing, and I want to store data in a binary heap.
Right now it's stored in an indexed table, like..
OpenSet[1] = { X, Y, Source, GScore, HScore, et cetera, et cetera...
Just a table with another table of information....
How would I use a binary heap, and would it be that much faster? Here's the code I use to create the map from terrain:
function GenerateMap(TerrainY) -- TerrainY is the height to scan it for. Scanning, not really generating. 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 print("It took: "..tick()-TimeTook.." seconds to complete the terrain capture") end
The point of this is to try to pre-calculate as much as I can, without lagging the server.
If I made a binary heap, how would it work? I mean, I'm indexing it by [X][Y] values, so...
|
|
|
| Report Abuse |
|
|
Sorcus
|
  |
 |
| Joined: 29 Nov 2010 |
| Total Posts: 3775 |
|
|
| 24 May 2012 04:01 PM |
Stravant has some data collected which proves that an array works just as well as a binary heap for A* in ROBLOX. Ping him.
~Sorcus |
|
|
| Report Abuse |
|
|
lah30303
|
  |
| Joined: 15 Feb 2008 |
| Total Posts: 10027 |
|
|
| 24 May 2012 04:10 PM |
I have done binary heaps before, but it wasn't very well written and it was 2 years ago so I don't remember it well. If you want to you can look at what I did in this model:
http://www.roblox.com/A-Pathfinder-with-binary-heaps-V-1A-item?id=22333228 |
|
|
| Report Abuse |
|
|
sncplay42
|
  |
| Joined: 27 Nov 2008 |
| Total Posts: 11891 |
|
|
| 24 May 2012 04:12 PM |
"Stravant has some data collected which proves that an array works just as well as a binary heap for A*"
I know you can store a binary heap in an array (see the wikipedia article on them)... |
|
|
| Report Abuse |
|
|
sncplay42
|
  |
| Joined: 27 Nov 2008 |
| Total Posts: 11891 |
|
|
| 24 May 2012 04:13 PM |
| And for the record that's what I use in my AI system. |
|
|
| Report Abuse |
|
|
Sorcus
|
  |
 |
| Joined: 29 Nov 2010 |
| Total Posts: 3775 |
|
|
| 24 May 2012 04:13 PM |
I wasn't saying that he implementing a binary heap in an arry >> I was saying a regular array performs just as well.
~Sorcus |
|
|
| Report Abuse |
|
|
Quenty
|
  |
| Joined: 03 Sep 2009 |
| Total Posts: 9316 |
|
|
| 24 May 2012 05:00 PM |
Hmm... thanks.
I seem to be having trouble implimenting my A* in a way that it's efficient with the indexing stuffz.
I'm having indecision on how to store information... Uggg... |
|
|
| Report Abuse |
|
|
Quenty
|
  |
| Joined: 03 Sep 2009 |
| Total Posts: 9316 |
|
|
| 24 May 2012 05:08 PM |
I think that using a metatable to find if an index exists is getting just a bit confusing....
Uggg...
This is what I've tried...
- Using the 'Table' of the node itself as an index. However, this meant I had to either use some fancy metatable hack, or copy a table of 100,000 or so values every call...
- Using tables with [X][Y] indexs...
I'm trying the tables thing again...
I'm pretty sure I don't want to talk about the other thing's I've tried. |
|
|
| Report Abuse |
|
|
MajorTyco
|
  |
| Joined: 09 Apr 2010 |
| Total Posts: 1989 |
|
|
| 24 May 2012 05:15 PM |
Inferring from the article on Wikipedia about binary heaps, it seems that it would be much easier and more efficient, or at least just as efficient, to just use an array- as Sorcus posted.
"I remain just one thing, and one thing only — and that is a clown. It places me on a far higher plane than any politician."-- Charlie Chaplin |
|
|
| Report Abuse |
|
|
smurf279
|
  |
| Joined: 15 Mar 2010 |
| Total Posts: 6871 |
|
|
| 24 May 2012 05:34 PM |
Tip:
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; X; X-1; X-1; X=1; X-1; X; X+1} Y = {Y+1; Y+1; Y+1; Y; Y; Y-1; Y-1; Y-1}; } end
Storing a table for X values and Y values is much more memory effecient than the alternative of storing a table for each ordered pair. This especially comes in handy when generating lists of coordinates like what you seem to be doing ^.^ |
|
|
| Report Abuse |
|
|