Grid "system", useful or not ? :S

[Komaqtion]

Hello

I just saw a little post about someone wanting to do something in a grid formation, and I thought I'd cook something up which would do just that

Well, the concept of this is actually done, and it works but I just wanted to get some pointers on how useful it would be to have a system like this, and also what I can do to make it more usable and configurable...

This is the code I have atm, and as you can see I've tried using a hashtable and an array to index the different squares you get in a grid. At first I really wanted to use an integer array which would contain the square-number of each grid-square and also the grid_square struct of those but since vJass can't really handle arrays inside structs (You have to specify the size of the array), I went another way.
I then tried using a hashtable for it, and use the Grid struct's integer number as the parent key, and the Grid_Square struct integer number for the child key, but I was unable to find a way to implement this into the Grid struct (I don't really wanna use globals) and I also found it hard to index it very well so I scrapped this too...

Anyways, code:

library Gridder

    globals
        //hashtable Grid_Hash
        
        //location array Square_Loc
    endglobals

    private keyword Grid

    struct Grid_Square
        real centerX
        real centerY
        real square_width
        real square_height
        
        Grid owningGrid
        
        static method create takes real x, real y, real width, real height, Grid belongto returns thistype
            local thistype this = thistype.allocate()
            
            set centerX = x
            set centerY = y
            set square_width = width
            set square_height = height
            
            set owningGrid = belongto
            
            return this
        endmethod
        
    endstruct

    struct Grid
        real g_centerX = 0.
        real g_centerY = 0.
        real g_width = 0.
        real g_height = 0.
        real sq_width = 0.
        real sq_height = 0.
        
        integer g_squares = 0
        
        static method create takes real x, real y, integer h_number, integer v_number, real squarewide, real squarehigh returns thistype
            local thistype this = thistype.allocate()
            local integer i = 0
            local integer i1 = 0
            //local integer i2 = 0
            local real curX = 0.
            local real curY = 0.
            local real startX = x - ((squarewide * h_number) / 2.)
            local real startY = y + ((squarehigh * v_number) / 2.)
            
            set g_centerX = x
            set g_centerY = y
            set g_width = h_number * squarewide
            set g_height = v_number * squarehigh
            set g_squares = h_number * v_number
            set sq_width = squarewide
            set sq_height = squarehigh
            
            loop
                set i = i + 1
                set i1 = 0
                
                exitwhen i > v_number
                
                set curY = startY - (squarehigh * i)
                
                //call DisplayTimedTextToPlayer( GetLocalPlayer(), 0., 0., 60., "Y: " + R2S( curY ) )
                
                loop
                    set i1 = i1 + 1
                    
                    exitwhen i1 > h_number
                    
                    set curX = startX + (squarewide * i1)
                    
                    call Grid_Square.create( curX, curY, squarewide, squarehigh, this )
                    
                    //call SaveLocationHandle( Grid_Hash, this, Grid_Square.create( curX, curY, squarewide, squarehigh, this ), Location( curX, curY ) )
                    
                    //call DisplayTimedTextToPlayer( GetLocalPlayer(), 0., 0., 60., &quot;X: (&quot; + I2S( i2 ) + &quot;<img src="data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7" class="smilie smilie--sprite smilie--sprite1" alt=":)" title="Smile    :)" loading="lazy" data-shortname=":)" /> &quot; + R2S( curX ) )
                    
                    //call AddSpecialEffect( &quot;Abilities\\Spells\\NightElf\\Barkskin\\BarkSkinTarget.mdl&quot;, curX, curY )
                    
                    //set i2 = i2 + 1
                endloop
                
            endloop
            
            //call DisplayTimedTextToPlayer( GetLocalPlayer(), 0., 0., 60., &quot;StartX: &quot; + R2S( startX ) )
            //call DisplayTimedTextToPlayer( GetLocalPlayer(), 0., 0., 60., &quot;StartY: &quot; + R2S( startY ) )
            //call DisplayTimedTextToPlayer( GetLocalPlayer(), 0., 0., 60., &quot;CenterX: &quot; + R2S( x ) )
            //call DisplayTimedTextToPlayer( GetLocalPlayer(), 0., 0., 60., &quot;CenterY: &quot; + R2S( y ) )
            
            return this
        endmethod
        
        private static method onInit takes nothing returns nothing
            local thistype this = thistype.create( 0., 0., 10, 10, 150., 150. )
            
            //set Grid_Hash = InitHashtable()
        endmethod
        
    endstruct
    
endlibrary

If any of you have any thoughts or ideas on this, please share them Good or bad

 

[Hatebreeder]

So, you're emulating a Grid for what exactly?

I can't see this being used for anything, since WC3 has a Grid of it's own?

Just cut down the X/Y in 64*64 or w/e and get the MaxX MaxY MinX MinY of the "grid cell"? (kinda hard to explain)

Anyways, this COULD be used for a Space Invaders kind of map ( well, one could deny all Group actions and instead loop through the grids to see if Projectile XY is in the same Grid as Enemy XY and do w/e actions ), but other than that I can't think of anything.

 

[Komaqtion]

Well, I thought that this could be used for easy and accurate grid-shapes for something you'd have to figure out for yourself.

And also, if you'd like to create a Chess game (Or Tic-Tac-Toe or something) then this would be ideal, right ?

Just cut down the X/Y in 64*64 or w/e and get the MaxX MaxY MinX MinY of the "grid cell"? (kinda hard to explain)

Not too sure I understand you there... :S

 

[Ashlebede]

Just cut down the X/Y in 64*64 or w/e and get the MaxX MaxY MinX MinY of the "grid cell"? (kinda hard to explain)

Not too sure I understand you there... :S

Read : Use rects. They already have MinX, MinY, MaxX, MaxY, CenterX, CenterY... you'd just have to create a couple functions to get their width & height, which is easy, anyways. Rects wouldn't take any more disk space than structs, as far as I know.

 

[Komaqtion]

Yeah, but the problem is still indexing...

I would like to store all those rects in that struct, but without having to specify an exact size :S

 

[Ashlebede]

Why don't you want to use globals, by the way ?

It seems that a hashtable is the only way to have an unlimited (or almost) number of elements in your data structure. If you really don't want to use globals, you could use a hashtable for each instance... (lol?)

You could also cycle through all of the struct instances of type 'Grid_Square', although complexity of actions would be a problem in such a case...

Hashtables are really the best option for an 'undefined size' array.

 

[Bribe]

Rects are handles and thus take up more space than a simple array all by themselves.

Eliminating a lot of handles is a great thing to learn because in 95% of scripts I see people posting on these warcraft sites can be optimized to use fewer handles or take advantage of already-existing handles.

 

[Komaqtion]

Yeah exactly, so that is why I would rather store everything in that Grid_Square struct, like maxx, minx centerx etc... But I just don't know how to connect those two together :S

 

[saw792]

Here, I made you a proper version with hashtables. I also made you a just-for-fun version using a linked list, which is horribly inefficient. I just like recursion

Hashtable version:

library HashTableGrid

    globals
        private hashtable gridtable = InitHashtable()
    endglobals
    
    struct Grid_Square
    
        real centerx
        real centery
        real width
        real height
        real maxx
        real maxy
        real minx
        real miny
        
        static method create takes real cx, real cy, real w, real h returns thistype
            local thistype this = thistype.allocate()
            local real halfwidth = w / 2.0
            local real halfheight = h / 2.0
            
            set centerx = cx
            set centery = cy
            set width = w
            set height = h
            
            set maxx = cx + halfwidth
            set maxy = cy + halfheight
            set minx = cx - halfwidth
            set miny = cy - halfheight
            
            return this
        endmethod
        
    endstruct
    
    struct Grid
    
        private real xoffset
        private real yoffset
        private real tilewidth
        private real tileheight
        private integer h
        private integer v
        
        //Starts at top left corner square for convenience
        static method create takes real    x,           real    y,                /*
*/                                 real    squarewidth, real    squareheight,     /*
*/                                 integer h_number,    integer v_number          /*
*/                                 returns thistype

            local thistype this = thistype.allocate()
            local integer i = 0
            local integer j = 0
            local real halfwidth = squarewidth / 2.0
            local real halfheight = squareheight / 2.0
            local Grid_Square temp
            local integer count = 0
            
            set xoffset = x
            set yoffset = y
            set tilewidth = squarewidth
            set tileheight = squareheight
            set h = h_number
            set v = v_number
            
            loop
                exitwhen j == v
                
                loop
                    exitwhen i == h
                    
                    set count = count + 1
                    set temp = temp.create(x + halfwidth + i * squarewidth, y + halfheight + j * squareheight, squarewidth, squareheight)
                    call SaveInteger(gridtable, this, count, temp)
                    
                    set i = i + 1
                endloop
                
                set i = 0
                set j = j + 1
            endloop
            
            return this
        endmethod
        
        //Takes grid coordinates, i.e. (5, 6) gives 5 squares across, 6 down
        //Starts at (1, 1) for some reason... I guess it's more intuitive
        method getSquare takes integer xcoord, integer ycoord returns Grid_Square
            return LoadInteger(gridtable, this, h * (ycoord - 1) + xcoord)
        endmethod
        
    endstruct
  
endlibrary

Linked List Just-For-Fun Version:

library Grid

    struct Grid_Square
    
        real centerx
        real centery
        real width
        real height
        real maxx
        real maxy
        real minx
        real miny
        private Grid_Square next = 0
        
        static method create takes real cx, real cy, real w, real h returns thistype
            local thistype this = thistype.allocate()
            local real halfwidth = w / 2.0
            local real halfheight = h / 2.0
            
            set centerx = cx
            set centery = cy
            set width = w
            set height = h
            
            set maxx = cx + halfwidth
            set maxy = cy + halfheight
            set minx = cx - halfwidth
            set miny = cy - halfheight
            
            return this
        endmethod
        
        method getNext takes nothing returns thistype
            return next
        endmethod
        
        method addSquare takes real cx, real cy, real w, real h returns nothing
            if next == 0 then
                set next = Grid_Square.create(cx, cy, w, h)
            else
                call next.addSquare(cx, cy, w, h)
            endif
        endmethod
        
        method deleteSquare takes nothing returns nothing
            if next.next == 0 then
                set next = 0
            else
                call next.deleteSquare()
            endif
        endmethod
        
        method getSquare takes integer whichSquare returns thistype
            if whichSquare == 1 then
                return this
            else
                return next.getSquare(whichSquare - 1)
            endif
        endmethod
        
    endstruct
    
    struct Grid
    
        private real xoffset
        private real yoffset
        private real tilewidth
        private real tileheight
        private integer h
        private integer v
        private Grid_Square first
        
        //Starts at top left corner square for convenience
        static method create takes real    x,           real    y,                /*
*/                                 real    squarewidth, real    squareheight,     /*
*/                                 integer h_number,    integer v_number          /*
*/                                 returns thistype

            local thistype this = thistype.allocate()
            local integer i = 0
            local integer j = 0
            local real halfwidth = squarewidth / 2.0
            local real halfheight = squareheight / 2.0
            local Grid_Square temp
            
            set xoffset = x
            set yoffset = y
            set tilewidth = squarewidth
            set tileheight = squareheight
            set h = h_number
            set v = v_number
            set first = Grid_Square.create(x + halfwidth, y + halfheight, squarewidth, squareheight)
            
            set i = i + 1
            set temp = first
            
            loop
                exitwhen j == v
                
                loop
                    exitwhen i == h
                    
                    call temp.addSquare(x + halfwidth + i * squarewidth, y + halfheight + j * squareheight, squarewidth, squareheight)
                    set temp = temp.getNext()
                    
                    set i = i + 1
                endloop
                
                set i = 0
                set j = j + 1
            endloop
            
            return this
        endmethod
        
        //Takes grid coordinates, i.e. (5, 6) gives 5 squares across, 6 down
        //Starts at (1, 1) for some reason... I guess it's more intuitive
        method getSquare takes integer xcoord, integer ycoord returns Grid_Square
            return h * (ycoord - 1) + xcoord
        endmethod
        
    endstruct
  
endlibrary

 

[Komaqtion]

Well, thank you but I would still like to know if there is another way, without using hashtables, or the likes ? :S

 

[saw792]

I just don't know what you are asking for and why hashtables aren't the answer. You can't "index" things without using arrays or hashtables, you can't make 2D arrays (or arrays within structs) dynamic, and any other simulated data structure like my linked list version is going to be crappy and inefficient for most purposes.

 

[Xienoph]

If it makes you feel better, The Big Game uses a grid system. Except ours uses a 3D grid.

What will be useful is a function that, given a coordinate, returns a Grid_Square (btw, why not use camel case?) that contains the coordinate.

EDIT: You can also use 2D arrays to make the grid. Not as slow as linked list, but offers compatibility with pre 1.24 that hashtable doesn't have.

 

[Komaqtion]

What will be useful is a function that, given a coordinate, returns a Grid_Square (btw, why not use camel case?) that contains the coordinate.

Hmm... I'm not too sure I understand completely what you mean here :S
You mean that you insert coordinates (X and Y) and out comes a new Grid_Square (GridSquare) ?

EDIT: You can also use 2D arrays to make the grid. Not as slow as linked list, but offers compatibility with pre 1.24 that hashtable doesn't have.

I don't actually know how to create/use these XD
An example ?

 

[Xienoph]

Hmm... I'm not too sure I understand completely what you mean here :S
You mean that you insert coordinates (X and Y) and out comes a new Grid_Square (GridSquare) ?

Yes. To be clear, this will be the function header:

function getGridSquare takes real x, real y returns GridSquare

This will be useful if you have a unit walking around and you want to know in which GridSquare the grid is currently in.

I don't actually know how to create/use these XD
An example ?

If you want to create a 2D array of int, you make ArrayOfInt[], where ArrayOfInt is a struct with an array of int (int[]). It doesn't enforce a block array, but you can wrap that around a struct that enforce that property.

 

[Komaqtion]

Yes. To be clear, this will be the function header:

function getGridSquare takes real x, real y returns GridSquare

This will be useful if you have a unit walking around and you want to know in which GridSquare the grid is currently in.

Well, what if there are more GridSquares in one place ? :S
Or, is it supposed to be a function, or a method ?
If a function maybe it can take another argument, Grid whichGrid, to specify this ? :S

If you want to create a 2D array of int, you make ArrayOfInt[], where ArrayOfInt is a struct with an array of int (int[]). It doesn't enforce a block array, but you can wrap that around a struct that enforce that property.

I'll probably just go with hashtables instead, as it seems you still need to specify the size of that 2D array (Right ?)...

 

[Xienoph]

Well, what if there are more GridSquares in one place ? :S
Or, is it supposed to be a function, or a method ?
If a function maybe it can take another argument, Grid whichGrid, to specify this ? :S

Yes, it can be a method, a function which accepts Grid as an input parameter, function with uses a global Grid, or any other way. The point is, it returns a GridSquare that contains the given coordinate.

If it is possible to have GridSquares overlap, you can modify the function (or method, it doesn't matter) to return a list of GridSquare.

I'll probably just go with hashtables instead, as it seems you still need to specify the size of that 2D array (Right ?)...

Yep. I though I read that you didn't know how else to implement that ... but I guess I was seeing things.

 

[Komaqtion]

If it is possible to have GridSquares overlap, you can modify the function (or method, it doesn't matter) to return a list of GridSquare.

And how would I do that ? :S
You can only return a single struct...

EDIT: This is what I have now:

library Gridder

    globals
        public hashtable Hashtable
    endglobals

    private keyword Grid

    struct GridSquare
        real centerX
        real centerY
        real width
        real height
        
        real maxX
        real minX
        real maxY
        real minY
        
        Grid squareOwner
        
        static method create takes real CenterX, real CenterY, real Width, real Weight, Grid owner returns thistype
            local thistype this = thistype.allocate()
            
            set centerX = centerX
            set centerY = centerY
            set width = width
            set height = height
            
            set maxX = centerX + (width / 2)
            set minX = centerX - (width / 2)
            set maxY = centerY + (height / 2)
            set minY = centerY - (height / 2)
            
            set squareOwner = owner
            
            return this
        endmethod
        
    endstruct

    struct Grid
        real centerX = 0.
        real centerY = 0.
        real width = 0.
        real height = 0.
        real squareWidth = 0.
        real squareHeight = 0.
        
        integer numberSquares = 0
        
        static method create takes real x, real y, integer h_number, integer v_number, real squarewide, real squarehigh returns thistype
            local thistype this = thistype.allocate()
            local integer i = 0
            local integer i1 = 0
            local integer square_count = -1
            local real curX = 0.
            local real curY = 0.
            local real startX = x - ((squarewide * h_number) / 2.)
            local real startY = y + ((squarehigh * v_number) / 2.)
            
            set centerX = x
            set centerY = y
            set width = h_number * squarewide
            set height = v_number * squarehigh
            set numberSquares = h_number * v_number
            set squareWidth = squarewide
            set squareHeight = squarehigh
            
            loop
                set i = i + 1
                set i1 = 0
                
                exitwhen i > v_number
                
                set curY = startY - (squarehigh * i)
                
                loop
                    set i1 = i1 + 1
                    set square_count = square_count + 1
                    
                    exitwhen i1 > h_number
                    
                    set curX = startX + (squarewide * i1)
                    
                    call SaveInteger( Hashtable, this, square_count, GridSquare.create( curX, curY, squarewide, squarehigh, this ) )
                endloop
                
            endloop
            
            return this
        endmethod
        
        method getPointGridSquare takes real xCoordinate, real yCoordinate returns GridSquare
            local GridSquare square
            local integer i = -1
            
            loop
                set i = i + 1
                set square = LoadInteger( Hashtable, this, i )
                
                if ( square.maxX >= xCoordinate or square.minX <= xCoordinate ) and ( square.maxY >= yCoordinate or square.minY <= yCoordinate ) then
                    return square
                endif
                
            endloop
            
            return 0
        endmethod
        
        method getSquare takes integer xCount, integer yCount returns GridSquare
            return LoadInteger( Hashtable, this, ( yCount * 10 ) + xCount )
        endmethod
        
        private static method onInit takes nothing returns nothing
            debug local thistype this = thistype.create( 0., 0., 10, 10, 150., 150. )
            
            set Hashtable = InitHashtable()
        endmethod
        
    endstruct
    
endlibrary

Would this be correct ?

 

[Komaqtion]

Bump

 

[saw792]

Your getSquare method shouldn't have a constant 10, but be based on the number of horizontal grid squares.

Also, getPointGridSquare should be reduced to an O(1) complexity mathematical formula rather than the O(n) search you are doing now. I can't be bothered to work it out now though, maybe tomorrow. Sleep time...

 

[Komaqtion]

Your getSquare method shouldn't have a constant 10, but be based on the number of horizontal grid squares.

Oh, yeah XD Silly me

Also, getPointGridSquare should be reduced to an O(1) complexity mathematical formula rather than the O(n) search you are doing now. I can't be bothered to work it out now though, maybe tomorrow. Sleep time...

What do you mean here ? :S
(And what does O(1) and O(n) mean ? XD)