Server Help Forum Index Server Help
Community forums for Subgame, ASSS, and bots
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   StatisticsStatistics   RegisterRegister 
 ProfileProfile   Login to check your private messagesLogin to check your private messages   LoginLogin (SSL) 

Server Help | ASSS Wiki (0) | Shanky.com
Turning coordinates into a string efficiently

 
Post new topic   Reply to topic Printable version
 View previous topic  i need help Post :: Post Where can I throw this function in mer...  View next topic  
Author Message
grazzhoppa
Novice


Joined: Jan 03 2007
Posts: 29
Offline

PostPosted: Thu Aug 14, 2008 4:07 am    Post subject: Turning coordinates into a string efficiently Reply to topic Reply with quote

I have two methods of doing this: which do you believe is more CPU efficient for practical use? They are the same memory-usage wise.

The first involves:
    2 integer allocations and assignments
    2 integer divisions
    1 2D array lookup

The 2nd involves:
    most common cases: 6 to 14 integer comparisons. Best: 2 comparisons, Worst: 16 comparisons
    lots of return statements


These split the map into 25 sectors and return the appropriate description of a sector based on a given point on the map.
Code: Show/Hide

const char labels[5][5][30] = {
    { "Upper-Left Corner", "Far-Left Upward", "Far-Left Center", "Far-Left Downward", "Lower-Left Corner" },
    { "Far-Up Leftward", "Center Upper-Left", "Center Left", "Center Lower-Left", "Far-Down Leftward"},
    { "Far-Up Center", "Center Upward", "Center", "Center Downward", "Far-Down Center"},
    { "Far-Up Rightward", "Center Upper-Right", "Center Right", "Center Lower-Right", "Far-Down Rightward"},
    { "Upper-Right Corner", "Far-Right Upward", "Far-Right Center", "Far-Right Downward", "Lower-Right Corner"}
};
const char* GeneratePlayerCoordsString(uint16_t xpos_px, uint16_t ypos_px) {
    uint8_t hori = xpos_px / (16384/5); // gives 0 based index into labels[][] array.  It works on basis of integer division.
    uint8_t vert = ypos_px / (16384/5);
    return labels[hori][vert];
}

Code: Show/Hide

const char* GeneratePlayerCoordsString(uint16_t xpos_px, uint16_t ypos_px) {
    if(xpos_px < 3276) {
        if(ypos_px < 3276) return "Upper-Left Corner";
        else if((ypos_px >= 3276) && (ypos_px < 6553)) return "Far-Left Upward";
        else if((ypos_px >= 6553) && (ypos_px < 9830)) return "Far-Left Center";
        else if((ypos_px >= 9830) && (ypos_px < 13107)) return "Far-Left Downward";
        else if(ypos_px >= 13107) return "Lower-Left Corner";
    }
    else if((xpos_px >= 3276) && (xpos_px < 6553)) {
        if(ypos_px < 3276) return "Far-Up Leftward";
        else if((ypos_px >= 3276) && (ypos_px < 6553)) return "Center Upper-Left";
        else if((ypos_px >= 6553) && (ypos_px < 9830)) return "Center Left";
        else if((ypos_px >= 9830) && (ypos_px < 13107)) return "Center Lower-Left";
        else if(ypos_px >= 13107) return "Far-Down Leftward";
    }
    else if((xpos_px >= 6553) && (xpos_px < 9830)) {
        if(ypos_px < 3276) return "Far-Up Center";
        else if((ypos_px >= 3276) && (ypos_px < 6553)) return "Center Upward";
        else if((ypos_px >= 6553) && (ypos_px < 9830)) return "Center";
        else if((ypos_px >= 9830) && (ypos_px < 13107)) return "Center Downward";
        else if(ypos_px >= 13107) return "Far-Down Center";
    }
    else if((xpos_px >= 9830) && (xpos_px < 13107)) {
        if(ypos_px < 3276) return "Far-Up Rightward";
        else if((ypos_px >= 3276) && (ypos_px < 6553)) return "Center Upper-Right";
        else if((ypos_px >= 6553) && (ypos_px < 9830)) return "Center Right";
        else if((ypos_px >= 9830) && (ypos_px < 13107)) return "Center Lower-Right";
        else if(ypos_px >= 13107) return "Far-Down Rightward";
    }
    else if(xpos_px >= 13107) {
        if(ypos_px < 3276) return "Upper-Right Corner";
        else if((ypos_px >= 3276) && (ypos_px < 6553)) return "Far-Right Upward";
        else if((ypos_px >= 6553) && (ypos_px < 9830)) return "Far-Right Center";
        else if((ypos_px >= 9830) && (ypos_px < 13107)) return "Far-Right Downward";
        else if(ypos_px >= 13107) return "Lower-Right Corner";
    }
    return "Unknown Location";
}


The function that uses division is assembled into this:
Code: Show/Hide

__Z15IntegerDivisiontt:
   pushl   %ebp
   movl   %esp, %ebp
   subl   $8, %esp
   movl   8(%ebp), %eax
   movl   12(%ebp), %edx
   movw   %ax, -2(%ebp)
   movw   %dx, -4(%ebp)
   movzwl   -2(%ebp), %eax
   movl   %eax, %edx
   shrl   $2, %edx
   movl   $1342505041, %eax
   mull   %edx
   movl   %edx, %eax
   shrl   $8, %eax
   movb   %al, -5(%ebp)
   movzwl   -4(%ebp), %eax
   movl   %eax, %edx
   shrl   $2, %edx
   movl   $1342505041, %eax
   mull   %edx
   movl   %edx, %eax
   shrl   $8, %eax
   movb   %al, -6(%ebp)
   movzbl   -5(%ebp), %edx
   imull   $150, %edx, %edx
   movzbl   -6(%ebp), %ecx
   movl   %ecx, %eax
   sall   $4, %eax
   subl   %ecx, %eax
   addl   %eax, %eax
   addl   %eax, %edx
   addl   $_labels, %edx
   movl   %edx, %eax
   leave
   ret

The function that uses comparisons is assembled into this:
Code: Show/Hide

__Z17IntegerComparisontt:
   pushl   %ebp
   movl   %esp, %ebp
   subl   $8, %esp
   movl   8(%ebp), %eax
   movl   12(%ebp), %edx
   movw   %ax, -2(%ebp)
   movw   %dx, -4(%ebp)
   cmpw   $3275, -2(%ebp)
   ja   L3
   cmpw   $3275, -4(%ebp)
   ja   L4
   movl   $LC0, -8(%ebp)
   jmp   L2
L4:
   cmpw   $3275, -4(%ebp)
   jbe   L6
   cmpw   $6552, -4(%ebp)
   ja   L6
   movl   $LC1, -8(%ebp)
   jmp   L2
L6:
   cmpw   $6552, -4(%ebp)
   jbe   L8
   cmpw   $9829, -4(%ebp)
   ja   L8
   movl   $LC2, -8(%ebp)
   jmp   L2
L8:
   cmpw   $9829, -4(%ebp)
   jbe   L10
   cmpw   $13106, -4(%ebp)
   ja   L10
   movl   $LC3, -8(%ebp)
   jmp   L2
L10:
   cmpw   $13106, -4(%ebp)
   jbe   L13
   movl   $LC4, -8(%ebp)
   jmp   L2
L3:
   cmpw   $3275, -2(%ebp)
   jbe   L14
   cmpw   $6552, -2(%ebp)
   ja   L14
   cmpw   $3275, -4(%ebp)
   ja   L15
   movl   $LC5, -8(%ebp)
   jmp   L2
L15:
   cmpw   $3275, -4(%ebp)
   jbe   L17
   cmpw   $6552, -4(%ebp)
   ja   L17
   movl   $LC6, -8(%ebp)
   jmp   L2
L17:
   cmpw   $6552, -4(%ebp)
   jbe   L19
   cmpw   $9829, -4(%ebp)
   ja   L19
   movl   $LC7, -8(%ebp)
   jmp   L2
L19:
   cmpw   $9829, -4(%ebp)
   jbe   L21
   cmpw   $13106, -4(%ebp)
   ja   L21
   movl   $LC8, -8(%ebp)
   jmp   L2
L21:
   cmpw   $13106, -4(%ebp)
   jbe   L13
   movl   $LC9, -8(%ebp)
   jmp   L2
L14:
   cmpw   $6552, -2(%ebp)
   jbe   L25
   cmpw   $9829, -2(%ebp)
   ja   L25
   cmpw   $3275, -4(%ebp)
   ja   L26
   movl   $LC10, -8(%ebp)
   jmp   L2
L26:
   cmpw   $3275, -4(%ebp)
   jbe   L28
   cmpw   $6552, -4(%ebp)
   ja   L28
   movl   $LC11, -8(%ebp)
   jmp   L2
L28:
   cmpw   $6552, -4(%ebp)
   jbe   L30
   cmpw   $9829, -4(%ebp)
   ja   L30
   movl   $LC12, -8(%ebp)
   jmp   L2
L30:
   cmpw   $9829, -4(%ebp)
   jbe   L32
   cmpw   $13106, -4(%ebp)
   ja   L32
   movl   $LC13, -8(%ebp)
   jmp   L2
L32:
   cmpw   $13106, -4(%ebp)
   jbe   L13
   movl   $LC14, -8(%ebp)
   jmp   L2
L25:
   cmpw   $9829, -2(%ebp)
   jbe   L36
   cmpw   $13106, -2(%ebp)
   ja   L36
   cmpw   $3275, -4(%ebp)
   ja   L37
   movl   $LC15, -8(%ebp)
   jmp   L2
L37:
   cmpw   $3275, -4(%ebp)
   jbe   L39
   cmpw   $6552, -4(%ebp)
   ja   L39
   movl   $LC16, -8(%ebp)
   jmp   L2
L39:
   cmpw   $6552, -4(%ebp)
   jbe   L41
   cmpw   $9829, -4(%ebp)
   ja   L41
   movl   $LC17, -8(%ebp)
   jmp   L2
L41:
   cmpw   $9829, -4(%ebp)
   jbe   L43
   cmpw   $13106, -4(%ebp)
   ja   L43
   movl   $LC18, -8(%ebp)
   jmp   L2
L43:
   cmpw   $13106, -4(%ebp)
   jbe   L13
   movl   $LC19, -8(%ebp)
   jmp   L2
L36:
   cmpw   $13106, -2(%ebp)
   jbe   L13
   cmpw   $3275, -4(%ebp)
   ja   L48
   movl   $LC20, -8(%ebp)
   jmp   L2
L48:
   cmpw   $3275, -4(%ebp)
   jbe   L50
   cmpw   $6552, -4(%ebp)
   ja   L50
   movl   $LC21, -8(%ebp)
   jmp   L2
L50:
   cmpw   $6552, -4(%ebp)
   jbe   L52
   cmpw   $9829, -4(%ebp)
   ja   L52
   movl   $LC22, -8(%ebp)
   jmp   L2
L52:
   cmpw   $9829, -4(%ebp)
   jbe   L54
   cmpw   $13106, -4(%ebp)
   ja   L54
   movl   $LC23, -8(%ebp)
   jmp   L2
L54:
   cmpw   $13106, -4(%ebp)
   jbe   L13
   movl   $LC24, -8(%ebp)
   jmp   L2
L13:
   movl   $LC25, -8(%ebp)
L2:
   movl   -8(%ebp), %eax
   leave
   ret
Back to top
View users profile Send private message Add User to Ignore List
Dr Brain
Flip-flopping like a wind surfer


Age:38
Gender:Gender:Male
Joined: Dec 01 2002
Posts: 3502
Location: Hyperspace
Offline

PostPosted: Thu Aug 14, 2008 7:54 am    Post subject: Reply to topic Reply with quote

Unless you're doing this several million times a second, efficiency doesn't matter nearly as much as how long it takes YOU, the programmer, to implement it.
_________________
Hyperspace Owner

Smong> so long as 99% deaths feel lame it will always be hyperspace to me
Back to top
View users profile Send private message Add User to Ignore List AIM Address Yahoo Messenger MSN Messenger
Samapico
No, these DO NOT look like penises, ok?


Joined: May 08 2003
Posts: 1252
Offline

PostPosted: Thu Aug 14, 2008 5:36 pm    Post subject: Reply to topic Reply with quote

Yeah, don't waste several hours to save 2 seconds of processing time over 2 years... :/

Though the division thing with the array is interesting, and I think it's obviously the most efficient
_________________
(Insert a bunch of dead links here)
Back to top
View users profile Send private message Add User to Ignore List
Display posts from previous:   
Post new topic   Reply to topic    Server Help Forum Index -> Bot Questions All times are GMT - 5 Hours
Page 1 of 1

 
Jump to:  
You can post new topics in this forum
You can reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You can attach files in this forum
You can download files in this forum
View online users | View Statistics | View Ignored List


Software by php BB © php BB Group
Server Load: 668 page(s) served in previous 5 minutes.

phpBB Created this page in 0.601680 seconds : 29 queries executed (77.7%): GZIP compression disabled