WHAT IS THIS? OPTIMIZATIONS?

[Homicidal Monkey]

got bored today, so I optimized a few functions in EO2.0 server/client

server change log:
-greedy buffer allocation
-on-demand player timers

client change log:
-sorts character/npc/resources by y before rendering

client & server are compliant with EO2.0

**Current build**
[Download + Source](http://www.freemmorpgmaker.com/files/imagehost/pics/74b97929f8b65d43474d7220f6644939.zip)
**Old builds**
[b12.04.12: has possible y-bounds error](http://www.freemmorpgmaker.com/files/imagehost/pics/f0a43eee5de0ed4db0f4a00c5c6e162f.zip)

how it works:

>! original method implemented allocated room when needed and only allocated the amount needed. Assuming vb6 memory allocations are based on C memory allocations, growing an array actually results in:
>! * creating a new array
* filling the array with the old data
* deleting the original array
>! greedy method doubles the size of the buffer when more room is needed and then shrinks the buffer. Again, assuming vb6 memory allocations are based on C memory allocations, this results in:
>! * creating a new array
* filling the array with old data
* deleting the original array
>! so what's the difference? The passive-growth method has to reallocate the array every time a new element is added, while the greedy-growth method only has to when its out of room.
>! PS: assuming shrinking array uses similar algorithms to realloc in c, shrinking the array should run in O(1) time.

>! vanilla EO2.0's serverloop iterates through all the players at each loop interval when the timer is required for refresh. The only problem here really is that the significant digits is seconds, not 25ms. So instead of iterating each player's timers every 25ms, it iterates 1 player timer every loop. This results in a cost function: 25*O(1) where as original had O(n).
>! significance: input n>25 and it runs better. (where n is number of players). This method was implemented in a few other areas involving timers.

>! to properly display characters, EO2.0 iterates across a maps y-axis and then iterates across each character, npc, resource.
>! why this is bad: assume tiles-down is 11 and 75 players (predefined max). This results in a total of 75*75*75*75*…*75 = 75^11 operations just to check if it needs to draw a player. (its 30^11 for npc, no idea what max is for resoures)
>! how it works: counting sort.
for each y value, it counts each character, npc, resource at that location and saves the index. This results in (assuming 75 characters, 30npc, 10 resources, 11 tiles-down):
reset arrays: 3*11
counting: 75 + 30 + 10
drawing: 75 + 30 + 10
>! I haven't been able to test performance gain for this, but it should be significant if you have over 2 players on a map. 1 player on a map renders at approx same speed as before. Assuming internet isn't limiting factor, you could (in theory) have a map with 1 character per square, without lagging.
>! note: bandwidth consumption in Eclipse is still a n^2 function.
Also, this optimization is more in-place for potential reports. vb6 2D arrays are horribly optimized

I'll do some more fixes later, maybe. From what I remember, AI is horrible.

[zenmen]

damn! great news, small but great. Thank you, just downloading :)

[Homicidal Monkey]

Just a slight clarification:
the counting sort vs iteration is really 2n vs yn, where y is total squares in y-direction (>=11)
performance gain is really only going to be seen on really big/dense maps

[Displaced]

how does the greedy buffer know where to cut? if you have a long there and it's sorted XX 00 00 00, you would cut it down to a byte if you trunc where 0 begins. Or am I wrong?

[erkro1]

I get Subscript out of range 9 error when logging in.

He's selecting:
```
For i = 0 To playerCount(y) - 1
```In Render_Graphics.

y = -1

[Homicidal Monkey]

@Kamii:

> how does the greedy buffer know where to cut? if you have a long there and it's sorted XX 00 00 00, you would cut it down to a byte if you trunc where 0 begins. Or am I wrong?

it keeps track of where to write the next byte. So when it cuts off, it just sets buffersize = writehead-1
@Erwin:

> I get Subscript out of range 9 error when logging in.
>
> He's selecting:
> ```
> For i = 0 To playerCount(y) - 1
> ```In Render_Graphics.
>
> y = -1

that's caused by the engine trying to guess where to start drawing. I just forgot to clamp minimum to 0 in that loop. A simple fix would be
```
if y < 0 then y = 0
```
btw, fixed and reuploaded. Check first post

[Whackeddie99]

Would I be able to open this and Vanilla EOv2 in a program that shows what the differences is, and add everything to my current client?

[Homicidal Monkey]

@Whackeddie:

> Would I be able to open this and Vanilla EOv2 in a program that shows what the differences is, and add everything to my current client?

its completely compatible

[Chief]

@Fabio:

> got bored today, so I optimized a few functions in EO2.0 server/client

I thought you were dead.

[Homicidal Monkey]

@Chief:

> I thought you were dead.

Close guess, just entered math overdrive this year. (9hrs of continuous post-calc math classes daily)

[Justn]

@Fabio:

> From what I remember, AI is horrible.

Yes you are correct. I love seeing this. Wish more people did stuff like this in the tutorials section instead of posting new features thanks bro

Edit: its kinda messed up though

[erkro1]

I'm really wondering if someone really looked at this, because the NPC's walking animation isn't showed and the collision detectment is weird, and no-one has noticed it yet?

EDIT: When you add an NPC to Map Properties it doesnt save it.

[Homicidal Monkey]

@Erwin:

> I'm really wondering if someone really looked at this, because the NPC's walking animation isn't showed and the collision detectment is weird, and no-one has noticed it yet?
>
> EDIT: When you add an NPC to Map Properties it doesnt save it.

from what I could tell, those are pre-existing problems.

[Justn]

No we were both testing and discussing it.. it was pretty bugged I can confirm all three things erwin mentioned did u log in to the new one u posted all those angels are on the map yet the npc list for the map is empty they don't walk they kinda glitch around and after I opened the map properties the angels were gone and I.couldnt add any other npcs and I could walk threw some

[Homicidal Monkey]

@Justn:

> No we were both testing and discussing it.. it was pretty bugged I can confirm all three things erwin mentioned did u log in to the new one u posted all those angels are on the map yet the npc list for the map is empty they don't walk they kinda glitch around and after I opened the map properties the angels were gone and I.couldnt add any other npcs and I could walk threw some

still doesn't change about it being a pre-existing problem. I encountered that issue when using vanilla EO2.0 source. Also I didn't touch packet info.

[Justn]

Did u test your upload? It's more than the common issues of EO its like something got messed up.. I don't have that issue with my project or a vanilla EO.. it was more than just simple lag it was unusable.. I tried getting it to work but I couldn't even save the maps :(

[Homicidal Monkey]

I didn't touch anything having to do with packet sending, AI, map storage, etc
the only things changed were loop optimizations. **All problems that EO2.0 had previously, still exist**

[Justn]

I marked all the changes you made to the source when I get home bro ill add it to.my project and see what's up but I really don't think those are previous issues and if they are then the edits made it 50x worse thanks for the feedback really need these performance fixes

[Justn]

Any news on this Fabio? :(

Edit: the serverloop stuff works.. the greedy buffers fix is causing the map editor properties to stop saving (npcs) and something is bugged with the ysorting.

[Homicidal Monkey]

I find it odd that it only affects saving npcs.

[Justn]

I agree.. what I did was first took each fix u made and individually added it to my project.. erwin also did this at the same time as me on MSN.. first I took the serverloop stuff everything seemed to work better.. next I took the greedy buffers fix and added it.. that's when I nocited the map editor problems I only found it affect the npc saving but erwin ran into other issues with the map editor as well. So I took the buffer edits out and it went back to normal… Next I went for the y sorting fix.. everything went good for the most part.. I encountered an error that the attack frame (movement made when pressing ctrl) was not shown on screen I just stood there.. however this was fixed when I equipped an item that had a paperdoll set to it.. maybe I missed something from ur source on that one.. but erwin encountered a different error when he added the y sorting.. he would get an runtime error and client crash when entering a map that had resources on it.. maybe he can better explain what happened on his end.. I'm just trying to help by reporting what I found.. maybe someone else can take a look at this aswell I think it would help everyone here since lag is a problem for most games here D:

Edit: after all that I went back to your download and replaced the bigger fix with the default and it fixed the map editor problem.. yet the walking animations for npcs was still messed up and collision detection was off..  not sure if that's cause of the y sorting cause those seem to be the only things I found issues with..

[erkro1]

Like Justn said I was trying out the y sorting thing, Rose and me have take a look at the code and fixed the map crashes, but now the sprites aren't showing up.

Here's the edited code, with y checks instead of x.
```
'perform a counting sort for player info
    If Not initVisiblePlayers Then
        ReDim visiblePlayers(0 To Map.MaxY, 0 To Player_HighIndex) As Long
        initVisiblePlayers = True
    ElseIf Not Player_HighIndex = UBound(visiblePlayers, 2) Then
        ReDim visiblePlayers(0 To Map.MaxY, 0 To Player_HighIndex) As Long
    End If

    If Not initVisibleNpcs Then
        ReDim visibleNpcs(0 To Map.MaxY, 0 To Npc_HighIndex) As Long
        initVisibleNpcs = True
    ElseIf Not Npc_HighIndex = UBound(visibleNpcs, 2) Then
        ReDim visibleNpcs(0 To Map.MaxY, 0 To Npc_HighIndex) As Long
    End If

    If Not initVisibleResources Then
        ReDim visibleResources(0 To Map.MaxY, NumResources) As Long
        initVisibleResources = True
    ElseIf Not NumResources = UBound(visibleResources, 2) Then
        ReDim visibleResources(0 To Map.MaxY, NumResources) As Long
    End If

    If Not initPlayerCount Then
        ReDim playerCount(0 To Map.MaxY) As Long
        initPlayerCount = True
    ElseIf Not Map.MaxY = UBound(playerCount) Then
        ReDim playerCount(0 To Map.MaxY) As Long
    End If

    If Not initNpcCount Then
        ReDim npcCount(0 To Map.MaxY) As Long
        initNpcCount = True
    ElseIf Not Map.MaxY = UBound(npcCount) Then
        ReDim npcCount(0 To Map.MaxY) As Long
    End If

    If Not initResourceCount Then
        ReDim resourceCount(0 To Map.MaxY) As Long
        initResourceCount = True
    ElseIf Not Map.MaxY = UBound(resourceCount) Then
        ReDim resourceCount(0 To Map.MaxY) As Long
    End If

    For y = 0 To Map.MaxY
        playerCount(y) = 0
        npcCount(y) = 0
        resourceCount(y) = 0
    Next y

    For i = 1 To Player_HighIndex
        If IsPlaying(i) And GetPlayerMap(i) = GetPlayerMap(MyIndex) Then
            If Player(i).x >= TileView.Left And Player(i).x <= TileView.Right Then
                visiblePlayers(Player(i).y, playerCount(Player(i).y)) = i  'mark player
                playerCount(Player(i).y) = playerCount(Player(i).y) + 1    'increment count at location
            End If
        End If
    Next
    For i = 1 To Npc_HighIndex
        If MapNpc(i).x >= TileView.Left And MapNpc(i).x <= TileView.Right Then
            visibleNpcs(MapNpc(i).y, npcCount(MapNpc(i).y)) = i
            npcCount(MapNpc(i).y) = npcCount(MapNpc(i).y) + 1
        End If
    Next
    If NumResources > 0 Then
        If Resources_Init Then
            For i = 1 To Resource_Index
                If MapResource(i).x >= TileView.Left And MapResource(i).x <= TileView.Right Then
                    visibleResources(MapResource(i).y, resourceCount(MapResource(i).y)) = i
                    resourceCount(MapResource(i).y) = resourceCount(MapResource(i).y) + 1
                End If
            Next i
        End If
    End If

    For y = TileView.top To TileView.Bottom
        If y > Map.MaxY Then Exit For
        If y >= 0 Then
            For i = 0 To playerCount(y) - 1
                Call BltPlayer(visiblePlayers(y, i))
            Next i
            For i = 0 To npcCount(y) - 1
                Call BltNpc(visibleNpcs(y, i))
            Next i
            For i = 0 To resourceCount(y) - 1
                Call BltMapResource(visibleResources(y, i))
            Next i
        End If
    Next
```