Village Distribution

[travo]

Ive been putting off asking this for a while now, but just cant figure out how I am going to do it. I have found next to nothing on the subject

I want to have each player be assigned a spot in the game land and that is where thay are situated. I can easily check if a spot is already occupied, but what I cannot do is work out how to actually distribute the villages.

My main thought is some sort of loop which will run along a spiral function depending on how many players have already joined the game. But I am not sure how to implement this, or if it is even possible.

I have also consiodered having a level editor coded in php, where I can place villages, etc, however I do not know how I would keep all of the players together, so they can actually play the game.

Does anyone have any ideas, or even links to ideas that would set me in the right direction?

Thanks

[karnedge]

I imagine you would be using a simple X,Y system for each village. You could do a spiral with random placement from the last coordinate...

x = ($x * cos($x));
y = ($y * sin($y));

where $x and $y would be the last coordinate placed
which you could then do a + rand(2,4) on those so have it not evenly placed.

I dont know if this is what you're asking, and I'm not sure if this is even correct as I'm not much of a math whiz. lol

[travo]

I dont think that would make a spiral, it would just place the village somewhere in a circle closer than the village we are basing it off.

I was thinking something like this:
angle = remainder of  players/360
radius = 1 + players/10

Those numbers would probably end up saved and just incremented, to save calculations

Use sin and cos to work out the coordinates of that angle and radius, round values. Then choose a spot randomly up to 2 units either way on x and y axis, and check for empty spot. If not empty, increase the angle.

Ive also had another idea, not sure how itll go so I didnt mention it before, but I figure I may as well.

We have a square, 10 units by 10 units. In this square, we must get 15 players. Once we have 15, then the square moves along. Howver Im not sure how or even if this would work.

[JGadrow]

Why not just pre-determine 'village locations' for each coordinate graph. Basically, this way you'd just have a list of locations and each time a player joins you simply pop the last item from the list.

[Barrikor]

Ive also had another idea, not sure how itll go so I didnt mention it before, but I figure I may as well.

We have a square, 10 units by 10 units. In this square, we must get 15 players. Once we have 15, then the square moves along. Howver Im not sure how or even if this would work.

That's close to what I've been thinking of for when I finally get around to making a game

For the "square" all you'd really need is to store extra would be the X,Y coordinates of the top left tile and also maybe a counter to know when the area reaches 15 villages. Once it reaches 15, you could just have a function that changes the "square's" X,Y coords (based whatever shape you want the map to expand in) and resets the counter.

[travo]

Why not just pre-determine 'village locations' for each coordinate graph. Basically, this way you'd just have a list of locations and each time a player joins you simply pop the last item from the list.

I have also considered this, but like I said, how do I make sure new players are created near eachother, instead of on the other side of the world?


About the moving square one... If we could get the square to move in a square spiral around the center of the world, it wouldnt be too bad would it?

To do that, the square needs to go down 1 right 1 up 2 left 2 down 3 right 3 up 4 left 4 etc.... Im sure we could code a way to keep track of where it is. Not right now though, I have to go out for the day. Ill have a go at somethiing when I get back.

[Barrikor]

About the moving square one... If we could get the square to move in a square spiral around the center of the world, it wouldnt be too bad would it?

To do that, the square needs to go down 1 right 1 up 2 left 2 down 3 right 3 up 4 left 4 etc.... Im sure we could code a way to keep track of where it is. Not right now though, I have to go out for the day. Ill have a go at somethiing when I get back.

One thing to look at would be the circle drawing algorithms that drawing programs use...

Ex: http://www.cs.unc.edu/~mcmillan/comp136/Lecture7/circle.html

[JGadrow]

I have also considered this, but like I said, how do I make sure new players are created near eachother, instead of on the other side of the world?

You store them in a database table in the order that you want them created. So, id 1 is the first to be created, id 2 is the second, id 3 is the third, etc. Here's an example table:

Code: (sql) [Select]

CREATE TABLE village_new_location (id int unsigned not null auto_increment, xcoord int unsigned not null, ycoord int unsigned not null, primary key(id));
Then, when you want the next village to create you simply select the lowest one:

Code: (sql) [Select]

SELECT id, xcoord, ycoord FROM village_new_location ORDER BY id ASC LIMIT 1;
Once you're certain that the new village is created, you delete its corresponding record from the new village table:

Code: (sql) [Select]

DELETE FROM village_new_location WHERE id = '[lastIdValue]';

[travo]

That would work surprisingly easy...

Well coding wise, anyway... Keeping it updated could be a pain but it sounds alright. But it should be easy to make an ajax gui, it would just be my map class with a few addons...

Actually that sounds really good, because I was planning on having abandoned bases, so upon registering, I could randomly pop 1 or 2 of as abandons...

Just a thought.... Would they have to be entered in order of distance? Couldnt we have a distance column, and sort by that? Because that way, rather than slowly spiraling around the group, I could just add a heap of villages, it would still work... How much time do I lose for sorting by a coulumn which is not a primary index? I could just create a generaic index on it yeah?

[JGadrow]

The actual table definition was an example only. Obviously you can put anything in it that you wanted. I was just giving a fairly minimal test case.

As far as storing distance, I would avoid that if you're also storing coordinates because the distance could be calculated from the coordinates. This, of course, aides you in reaching Third Normal Form (3NF) for your database.

[travo]

Wouldnt it be too resource intensive to run

Code: [Select]

SELECT * FROM test ORDER BY (SQRT(POW(x,2)+POW(y,2))); every time someone registers though?

Or should I run

Code: [Select]

ALTER TABLE test ORDER BY (SQRT(POW(x,2)+POW(y,2))); every time I add new villages?

That would redo the natural order of the table, right?

I just ran a few tests, it reorders by distance perfectly, just a little slow, but not that much....I only noticed it when i reordered 2000 rows, even then, it was just a couple of seconds, just noticeable when your used to instant queries   I would just have to change it a little, because (0,0) will not be the center of my world.

Thanks guys

[famulus]

When comparing distance calculations, you can do without the sqrt, which might speed things up a bit depending on how many records you have.

[travo]

Good point, I didnt think about that

[JGadrow]

There's many solutions for dealing with calculations to preserve 3NF. While it's a bit OT, you'll probably benefit a bit from reading this blog post regarding 3NF.

However, I'll state that the solution he provides still feels like a violation of 3NF because the data is still in the table... It looks to me like he discounts the view solution because he couldn't find a proper method of managing his views even though it's, likely, the most proper solution.

[codestryke]

Trying to keep with normalization in database design should be a goal, normalization itself though is NOT very fast. The rules of normalization were created by database people for databases, not for programmers accessing databases, something to always keep in mind. In none of the rules of normalization does the word speed or performance get mentioned.

With all the games I've coded I've often broke many of the normalization rules so I could get performance. Joins are nice but joins cost both processing time, memory and heavy disk access when updating the tables.

Use what works best, not to try and achieve some arcane xNF rule LOL if you know my past there is a bunch of people in Redmond that just felt a shiver up there spine for me saying such things.

[Chris]

With all the games I've coded I've often broke many of the normalization rules so I could get performance. Joins are nice but joins cost both processing time, memory and heavy disk access when updating the tables.

Can not agree more. I always break one normalisation rule in all my games (repeated username in many tables). Althrough, you should not go berserk and disregard all the rules, normalisation is useful it's just you should not follow if blindly.

there is a bunch of people in Redmond that just felt a shiver up there spine for me saying such things.

Yeah, your perspective and willingness to follow artificial rules changes when you know that if your server breaks down you will not have enough food for dinner each morning

[JGadrow]

As far as performance, that's kind of where Database Views come into play, however, I agree that normalization is something to look at on a per-case basis.