Grid "system", useful or not ? :S

[saw792]

Big O notation (eg: O(1), O(n), O(n^2), O(log n) etc) is a way you can represent the complexity of an algorithm or operation, in other words how well it scales.

For example, right now every time getPointGridSquare is called it will run the code inside the loop once for every square until it finds the correct square. That's called a linear search, i.e. you search through every element until one satisfies the condition in counting order. This means that with a grid of n squares it will take on average n/2 time to find the correct square (sometimes over, sometimes under). Thus the amount of time it takes for your algorithm to find the correct square increases linearly with an increase in the number of squares on the grid. So if you double the number of squares you double the (average) amount of time it takes for your code to run. Thus O(n) is used to describe your algorithm as it is a linear relationship between time to run and number of squares.

My approach is to find a mathematical way of calculating which square the coordinates will be in. This means that regardless of the number of grid squares in the grid it will take the same amount of time to find the correct square. Thus an algorithm of that sort would be O(1), as the time taken is constant regardless of the number of grid squares n.

EDIT: getPointGridSquare:

method getPointGridSquare takes real xcoord, real ycoord returns GridSquare
    local real x0 = centerX - (width/2.0)
    local real y0 = centerY + (height/2.0)
    return getSquare(R2I((xcoord - x0)/squareWidth), R2I((ycoord - y0)/squareheight))
endmethod

Oh and your getSquare method should have some error checking to make sure the coordinates actually exist in the grid. That way getPointGridSquare doesn't need to duplicate the checks.

 

[Komaqtion]

Big O notation (eg: O(1), O(n), O(n^2), O(log n) etc) is a way you can represent the complexity of an algorithm or operation, in other words how well it scales.

For example, right now every time getPointGridSquare is called it will run the code inside the loop once for every square until it finds the correct square. That's called a linear search, i.e. you search through every element until one satisfies the condition in counting order. This means that with a grid of n squares it will take on average n/2 time to find the correct square (sometimes over, sometimes under). Thus the amount of time it takes for your algorithm to find the correct square increases linearly with an increase in the number of squares on the grid. So if you double the number of squares you double the (average) amount of time it takes for your code to run. Thus O(n) is used to describe your algorithm as it is a linear relationship between time to run and number of squares.

My approach is to find a mathematical way of calculating which square the coordinates will be in. This means that regardless of the number of grid squares in the grid it will take the same amount of time to find the correct square. Thus an algorithm of that sort would be O(1), as the time taken is constant regardless of the number of grid squares n.

Thanks for this explanation (Although Bribe already threw me a PM explaning this already XD) it was very helpful !

EDIT: getPointGridSquare:

method getPointGridSquare takes real xcoord, real ycoord returns GridSquare
    local real x0 = centerX - (width/2.0)
    local real y0 = centerY + (height/2.0)
    return getSquare(R2I((xcoord - x0)/squareWidth), R2I((ycoord - y0)/squareheight))
endmethod

Shouldn't that inline ?

Oh and your getSquare method should have some error checking to make sure the coordinates actually exist in the grid. That way getPointGridSquare doesn't need to duplicate the checks.

Well, 'getSquare' will just return 0 as the GridSquare struct if it doesn't exist, wouldn't it ? :S

 

[Bribe]

Shouldn't that inline ?

That won't inline because the "invisible" variable "this" is referenced more than once.

 

[Komaqtion]

Ok, well I haven't really understood what inlining means XD
Does:

    method getSquare takes integer xCount, integer yCount returns GridSquare
        return LoadInteger( Hashtable, this, ( yCount * heightSquares ) + xCount )
    endmethod

that inline ?

And also:

Well, 'getSquare' will just return 0 as the GridSquare struct if it doesn't exist, wouldn't it ? :S

 

[Bribe]

method getSquare takes integer xCount, integer yCount returns GridSquare
    return LoadInteger(Hashtable, this, yCount * this.heightSquares + xCount)
endmethod

"this" is referenced twice. Any parameters can only be referenced once.

method guy takes nothing returns nothing
    local integer i=0
    call DoNothing()
endmethod

In the above example, "this" is not even referenced, though it would not inline, because there are two lines of code.

method return0 takes nothing returns integer
    return 0
endmethod
//
set this = return0()

The above example inlines, as it has only one line and it does not reference any parameters more than once.

 

[Komaqtion]

Oh, ok Thanks

Ok, this is what I have atm, is it good ?

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
        integer squareNumber
        
        //effect array outlineSFX [8190]
        
        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
        
        method outlineSquare takes integer lineEffects, string whichEffect returns nothing
            
        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
        integer heightSquares = 0
        integer widthSquares = 0
        
        static method create takes real x, real y, integer h_number, integer w_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 * w_number) / 2.)
            local GridSquare square
            
            set centerX = x
            set centerY = y
            set width = h_number * squarewide
            set height = w_number * squarehigh
            set numberSquares = h_number * w_number
            set squareWidth = squarewide
            set squareHeight = squarehigh
            set heightSquares = h_number
            set widthSquares = w_number
            
            loop
                set i = i + 1
                set i1 = 0
                
                exitwhen i > w_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)
                    set square = GridSquare.create( curX, curY, squarewide, squarehigh, this )
                    
                    call SaveInteger( Hashtable, this, square_count, square )
                endloop
                
            endloop
            
            return this
        endmethod
        
        method getPointGridSquare takes real xcoord, real ycoord returns GridSquare
            local real x0 = centerX - (width/2.0)
            local real y0 = centerY + (height/2.0)
            
            return getSquare(R2I((xcoord - x0)/squareWidth), R2I((ycoord - y0)/squareHeight))
        endmethod
        
        method getSquare takes integer xCount, integer yCount returns GridSquare
            return LoadInteger( Hashtable, this, ( yCount * heightSquares ) + xCount )
        endmethod
        
        method onDestroy takes nothing returns nothing
            local integer i = -1
            local GridSquare square = 0
            
            loop
                set i = i + 1
                exitwhen i >= numberSquares
                
                set square = LoadInteger( Hashtable, this, i )
                
                call square.destroy()
            endloop
            
            call FlushChildHashtable( Hashtable, this )
        endmethod
        
        private static method onInit takes nothing returns nothing
            debug local thistype this
            debug local GridSquare square
            
            set Hashtable = InitHashtable()
            
            debug set square = getPointGridSquare( -562., 153 )
            debug set this = thistype.create( 0., 0., 10, 10, 150., 150. )
            debug call DestroyEffect( AddSpecialEffect( "Abilities\\Spells\\Human\\Thunderclap\\ThunderClapCaster.mdl", square.centerX, square.centerY ) )
        endmethod
        
    endstruct
    
endlibrary

 

[saw792]

Yeah it will return 0, but 0 also refers to a valid grid square...

 

[Komaqtion]

It returns the entire struct, not the number it is in the grid, so a struct's value can't be 0, right ?

 

[saw792]

Yeah you're right I was thinking of the input to LoadInteger not what the data is.

 

[Komaqtion]

It's ok

 

[Komaqtion]

So, what do you think, is this good, or better yet is it good enough for an approvable resource ?
(Though personally I think it has way too few features, so I would be glad to hear some ideas for them )

And I also added a method to the GridSquare struct:
[ljass]method outlineSquare takes integer lineEffects, string whichEffect returns nothing[/ljass]

Which is supposed outline the targetted square with effects by using some maths and such but I can't find a good way of doing this without making those effects leak as I can't store them in a variable... :S
Should I just use the hashtable again here, or what do you think ?

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
        integer squareNumber
        
        //effect array outlineSFX [8190]
        
        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
        
        method outlineSquare takes integer lineEffects, string whichEffect returns nothing
            
        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
        integer heightSquares = 0
        integer widthSquares = 0
        
        static method create takes real x, real y, integer h_number, integer w_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 * w_number) / 2.)
            local GridSquare square
            
            set centerX = x
            set centerY = y
            set width = h_number * squarewide
            set height = w_number * squarehigh
            set numberSquares = h_number * w_number
            set squareWidth = squarewide
            set squareHeight = squarehigh
            set heightSquares = h_number
            set widthSquares = w_number
            
            loop
                set i = i + 1
                set i1 = 0
                
                exitwhen i > w_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)
                    set square = GridSquare.create( curX, curY, squarewide, squarehigh, this )
                    
                    call SaveInteger( Hashtable, this, square_count, square )
                endloop
                
            endloop
            
            return this
        endmethod
        
        method getPointGridSquare takes real xcoord, real ycoord returns GridSquare
            local real x0 = centerX - (width/2.0)
            local real y0 = centerY + (height/2.0)
            
            return getSquare(R2I((xcoord - x0)/squareWidth), R2I((ycoord - y0)/squareHeight))
        endmethod
        
        method getSquare takes integer xCount, integer yCount returns GridSquare
            return LoadInteger( Hashtable, this, ( yCount * heightSquares ) + xCount )
        endmethod
        
        method onDestroy takes nothing returns nothing
            local integer i = -1
            local GridSquare square = 0
            
            loop
                set i = i + 1
                exitwhen i >= numberSquares
                
                set square = LoadInteger( Hashtable, this, i )
                
                call square.destroy()
            endloop
            
            call FlushChildHashtable( Hashtable, this )
        endmethod
        
        private static method onInit takes nothing returns nothing
            debug local thistype this
            debug local GridSquare square
            
            set Hashtable = InitHashtable()
            
            debug set square = getPointGridSquare( -562., 153 )
            debug set this = thistype.create( 0., 0., 10, 10, 150., 150. )
            debug call DestroyEffect( AddSpecialEffect( "Abilities\\Spells\\Human\\Thunderclap\\ThunderClapCaster.mdl", square.centerX, square.centerY ) )
        endmethod
        
    endstruct
    
endlibrary

 

[saw792]

Now a linked list might be useful

struct GridEffect
    effect e
    GridEffect next = 0

    static method create takes real x, real y, string path returns thistype
        local thistype this = thistype.allocate
        //set e = AddSpecialEffect(...)
    endmethod

    method add takes real x, real y, path returns GridEffect
        if next == 0 then
            set next = thisttype.create(x, y, path)
            return next
        else
            return next.add(x, y, path)
        endif
    endmethod

    method onDestroy takes nothing returns nothing
        call DestroyEffect(e)
        call next.destroy()
    endmethod
endstruct

struct GridSquare
        real centerX
        real centerY
        real width
        real height
        
        real maxX
        real minX
        real maxY
        real minY
        
        Grid squareOwner
        integer squareNumber
        
        GridEffect first
        
        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
        
        method outlineSquare takes integer lineEffects, string whichEffect returns nothing
            local integer i = 0
            local GridEffect ge = ge.create(...)//whereever the first effect should go
            set first = ge

            loop
                exitwhen you've finished making effects

                ge = ge.add(...)//wherever it goes
                
            endloop
        endmethod

        method onDestroy takes nothing returns nothing
            first.destroy()
        endmethod
            
        
    endstruct

//and ur usual grid stuff

It actually makes sense to do it this way this time, since you only need add/remove and not insert/read at random position in the list

 

[Troll-Brain]

So, what do you think, is this good, or better yet is it good enough for an approvable resource ?

A little advice, make a ressource only if you enjoy the simple fact to make it or will use it for sure, don't attempt it will be used by other peoples, especially if it's only for theoric purposes and you even don't plan to use it yourself.

Cool != usefull.

Hmm or it's just my personal story, i dunno

 

[Komaqtion]

Actually, I rarely make maps myself, and almost all of my "resources" come from questions here on the forum, though there may be just a single post which asks for something like it but if I think I can make it I'll do it

 

[Troll-Brain]

It's fine as long as you enjoy making it, i just wanted to say "don't be disappointed if nobody use your resource"

 

[mylemonblue]

I quickly read over the thread and still am not entirely sure what sort of grid it is (I figure it means like chess, as mentioned earleir). But can it be used to recreate games like Heroscape or Final Fantasy Tactics?

Both are grid based, and that's the first thing that came to mind when I saw the title.

*PS: Thanks for the help on the average levels thing*

 

[Komaqtion]

It's fine as long as you enjoy making it, i just wanted to say "don't be disappointed if nobody use your resource"

Yeah, I know... Thanks anyways

I quickly read over the thread and still am not entirely sure what sort of grid it is (I figure it means like chess, as mentioned earleir). But can it be used to recreate games like Heroscape or Final Fantasy Tactics?

Well, I'm just giving you the battlefield layout, you may utilize it as you wish after that
I'm just not completely done with it yet as there are still some features missing (As the above mentioned outlining-problem and I also want to add a method for creating a rect in each square )

*PS: Thanks for the help on the average levels thing*

Np