Jump to content
SubSpace Forum Network

Brackets

DeadlySoldier!!

By DeadlySoldier!!
in General Discussion

 Share

Recommended Posts

DeadlySoldier!! Newbie

DeadlySoldier!!

Posted
  • Author
Posted
I was thinking you could just do a if (p->tile.x == blablabla) stuff and then make it warp them, but yeah man thats -*BAD WORD*-a confusing after i thought about it you have to make it check wich squares are open and which arent, what duel boxes are being used andwat arent.. blah blum.gif
divine.216 Newbie

divine.216

Posted
Posted

I wrote the brackets bot that is used in eg and aswz. There was not too much of it that is too complicated (binary trees lend themselves to recursive solutions if you are comfortable with them). The only part where it became a bit complicated was in the arrangement of players within the tournament such that it could start at any time while at the same time minimizing the number of "bye"s that any player would receive: ie, when you have 4 players you don't want one player to get a bye to the finals while the other 3 fight amongst each other... similarly you don't want 2 people to get byes to the semifinals in a tournament of 16 and have the other 14 fight amongst each other etc.

 

I came up with a generic solution to this problem that I thought was pretty nifty and elegant. After some pondering and a little scientific inquiry (sitting thoughtfully on my throne in the bathroom) I noticed that the path to the appropriate box in an ideal configuration was simply the interpretation of the current player count as the binary path to the appropriate node -- from least to most significant. That is to say, if there are 4 rounds, and 0 players already joined, then the appropriate path to the next node is given by the 4 digit binary representation of 0: 0000, LEFT LEFT LEFT LEFT. Similarly, if there are 5 rounds and 6 players already joined, then the appropriate path to the next node is given by the 5 digit binary representation of 6: 00110, LEFT RIGHT RIGHT LEFT LEFT. This was a pretty neat observation and leads to an elegant and scalable solution. Given the number of players ('count') and the number of total rounds ('rounds') in the tournament, the appropriate box for the next player to be placed into ('box') is calculated as follows:

 

If you're storing the binary tree as an array, where the root is at index 0 and all left children are in index*2+1 and right children are in index*2+2.

int i,j,box;

for(box=0,i=1,j=(1<<rounds);i<j;box*=2,box+=1+!!(count&i),i<<=1);

 

Or if you are using a linked list representation of a binary tree, here is some pseudo-code, that should be a little more straightforward than the preceeding:

Node *NextNode(int count, Node *root)

{

Node *node = root;

foreach(bit in count from least to most significant){

 if(!node->left || !node->right) return node;

 if(bit == 1)

	 Node = node->right;

 else

	 Node = node->left;

}

}

 

If you didn't follow that here's a (hopefully) simplified explanation:

For each bit (from least to most significant) in the current player count, starting at the root of the tree you take a step to the left child if the bit is low and a step to the right child if the bit is high. After you have made a step for each round of the tournament, you will find yourself at the appropriate box for the next player in the tournament.

 

You may want to run some numbers through this, just to convince yourself that it works.

divine.216 Newbie

divine.216

Posted
Posted

PM has every right and responsibility to defend what he feels is his and/or his zone's.

brackets is mine and anyone is free to use it -- in fact I have given out the src to anyone who has asked w/ a decent reason.

 

Also, (and I don't suggest this for brackets because I'm already working on it) if you are going to clone bots, it might make sense to write them as ASSS modules instead of as bots. Especially if you are starting from scratch anyways.

PoLiX Newbie

PoLiX

Posted
Posted
I was talking to catid about the future of MERVBot and ASSS, and due to the fact it will still be bloody ez to make a merv dll (look at deadly's cluelessness in the post before this and he can make dlls), he may make a module for ASSS that loads merv dlls. So then they would still be able to be used, and you wouldnt need a bunch of bots running around.
Dustpuppy Newbie

»Dustpuppy

Posted
Posted
I found placing players in the right starting boxes easy enough (Thanks to divine for the algorithm), it was advancing players that caught me out. I tried 3 different methods and every time there were occasions when the bracket either froze (no duels) or there were too many people in the box.
divine.216 Newbie

divine.216

Posted
Posted

Here is my function for promoting a user.

You have to handle the case where someone advances but any number of preceeding duels of his future opponents may still be going.

 

Here are excerpts from a few data structs that I used:

#define PLAYERS_PER_BOX 2 // kind of silly, not a real magic number

typedef struct BoxT{

//... zero in .players[x][0] implies empty slot

char players[PLAYERS_PER_BOX][MAX_NAME_LEN+1];

//... removed some that is beyond scope of this

} BoxT,*Box;



#define MAXBOXCOUNT ((1 << MAXROUNDS)) // MAXROUNDS is arbitrary

typedef struct UDataT{

// ... more removed ...

int boxcount;

BoxT brackets[MAXBOXCOUNT];

// ... more removed ...

} UDataT,*UData;



// A player's main data struct is found by FP(name)

// A player's game info struct is found by GPI(data,p)

// where 'data' is the main bot data struct and p is the player data struct

typedef struct PInfoT{

// ... more removed...

int box; // id of the box they are in, else BOX_NONE

int player; // their player id in their box (0 or 1)

// ... more removed...

} PInfoT,*PInfo;

PInfo GPI(BotData *data,Player *p);



// Here are a few macros I used for the binary tree

#define PARENT(node) (((node)-1)/2)

#define LCHILD(node) ((node)*2+1)

#define RCHILD(node) ((node)*2+2)

#define ISLCHILD(node) ((node)%2)

#define ISRCHILD(node) (!((node)%2))

 

 

The function ContainsOpponents returns true if there is anyone in tree rooted at the given box.

int ContainsOpponent(UData ud,int box)

{

if(box > ud->boxcount-1) return 0;

if(ud->brackets[box].players[0][0] || ud->brackets[box].players[1][0]) return 1;

if(ContainsOpponent(ud,LCHILD(box)) || ContainsOpponent(ud,RCHILD(box))) return 1;

return 0;

}

 

The function PromoteBox is given a box id. It will correctly handle any promotions of player(s) in that box. If there are two players in the box it does nothing. If the box has no players, it does nothing. If the box has one player then it will first check to see if there are any pending duels that the one player is waiting for, by calling ContainsOpponents on the opposite child tree. If there are no opponents coming, it will advance the player to the next round and recursively call itself on the next box that it has advanced the player to.

 

void PromoteBox(BotData *data,UData ud,int box)

{

Player *p;

PInfo pi;

int oneopen=0,twoopen=0,containsopp;

if(box < 0) return;

if(!ud->brackets[box].players[0][0]) oneopen = 1;

if(!ud->brackets[box].players[1][0]) twoopen = 1;

containsopp = ContainsOpponent(ud,(twoopen ? RCHILD(box) : LCHILD(box)));

if(oneopen != twoopen && !containsopp){

 p = FP(ud->brackets[box].players[oneopen]);

 pi = GPI(data,p);

 if(pi){

	 if(!box){ // he wins it all (promoted past finals)

   pi->box = BOX_NONE;

   return;

	 }

	 pi->box = PARENT(box);



	 // copy his data to the next box, update his player info data

	 twoopen = ISRCHILD(box);

	 strncpy(ud->brackets[pi->box].players[twoopen],

   ud->brackets[box].players[pi->player],

   MAX_NAME_LEN);

	 ud->brackets[pi->box].players[twoopen][MAX_NAME_LEN] = 0;

	 pi->player = twoopen;



	 // physically move his ship to the next box

	 PutToSpot(data,ud,p); 

	 // clear out his name from the old box

	 ud->brackets[box].players[oneopen][0] = 0; 

	 // if he has an opponent waiting for him

	 if(ud->brackets[pi->box].players[!pi->player][0]){ 

   // ... start their match ...

   // ... code removed because beyond scope ...

	 }else{ 

   // he doesn't have an opponent waiting for him,

   // recursively try to promote him

   PromoteBox(data,ud,pi->box);

	 }

 }

}

}

 

Whenever a player is removed from the game for any reason (killed, quit, specced etc.) I simply do 

ud->brackets[pi->box].players[pi->player][0] = 0;

PromoteBox(data,ud,pi->box);

// ... check victory ...

// basically, if the opponent ends up with a box == BOX_NONE

// then he has won.

 

Hope that helps.

divine.216 Newbie

divine.216

Posted
Posted

I don't really think I can politely investigate the VB/Merv -> C/Pbot analogy so I'll refrain to avoid pissing off too many people (I'm in the wrong forum to be exploring that analogy).

 

That said, the reason I don't write a merv version of brackets is because I don't write merv plugins -- I am not intimate with the core's abstraction nor do I think it's really worth my time to become so. Lately, I have only been writing utility bots as needed for my zone and I won't undertake any large projects (either porting or from scratch) that aren't targeted towards ASSS.

Guest
This topic is now closed to further replies.
 Share
Go to topic listing
×
×
  • Create New...