Currently Online

Latest Posts

Topic: Completion of a map by symmetry

einstein13
Avatar
Joined: 2013-07-29, 00:01
Posts: 1118
Ranking
One Elder of Players
Location: Poland
Posted at: 2015-01-28, 14:43

gnarfk wrote:

1) In a edge , we have some algebrical informations (... altitude, bobs ...)

In my opinion we should think about the rotation of pure terrain first. Then we can think about other features. Filling the resources is quite fast. Much more faster than creating the terrain.

But altitude can be interpolated from non-approximated positions. So rotate the terrain we are interested in, then interpolate the heights of points. Without approximation of points.

2) The fields , we have the terrain type. you have to think the image of a field with your rotation. we have to find a way to keep neighbour fields neighbour ....

I had another- easier one - idea to do that. Steps to rotate:

  1. User: choose some points on the border of rotated land
  2. ? User: write the shape of the land (or: stright lines between the points? )
  3. Computer: Calculate the points posistions from point 1. and approximate it to map net
  4. Computer: Fill in the fields by specific type of terrain. Fields taken from inside the new shape taken from new points positions.

Possible features (I have ideas):

  • choose type of terrain (one? mix?)
  • choose flattening the borders to make them flat.
  • adding other parts, not only terrain: bobs, resources, etc. in the same amount as in the original shape
  • choose center point of rotation (around which we rotate)
  • while rotating we can draw a mask with lines according to rotated and beeing rotating shape.

But : if we find a solution for the 90° rotation (which may be particular enough to find a trick) , we will have solutions for any multiple of 30° .

For me 45 deg is more important:

2 players: 180=360 deg 3 players: 120=260 deg 4 players: 90 deg 6 players: 60 deg *8 players: 45 deg

30 deg is for 12 players, but can be used in other ways, as well as other possibilities. (part of map has some kind of symmetry, other parts aren't the same.)

I like 8-players maps. Then I can play for a loooong time with the AI and like the game (I don't like short games).


einstein13
calculations & maps packages: http://wuatek.no-ip.org/~rak/widelands/
backup website files: http://kartezjusz.ddns.net/upload/widelands/

Top Quote
gnarfk
Avatar
Topic Opener
Joined: 2015-01-05, 16:18
Posts: 70
Ranking
Likes to be here
Location: France
Posted at: 2015-01-28, 17:22

einstein13 wrote:

2) The fields , we have the terrain type. you have to think the image of a field with your rotation. we have to find a way to keep neighbour fields neighbour ....

I had another- easier one - idea to do that. Steps to rotate:

  1. User: choose some points on the border of rotated land
  2. ? User: write the shape of the land (or: stright lines between the points? )
  3. Computer: Calculate the points posistions from point 1. and approximate it to map net
  4. Computer: Fill in the fields by specific type of terrain. Fields taken from inside the new shape taken from new points positions.

are you sure that your new shape will have the same number of edges ? i think it is the most important . and i don't think it will be easy to have this.

But : if we find a solution for the 90° rotation (which may be particular enough to find a trick) , we will have solutions for any multiple of 30° .

For me 45 deg is more important:

2 players: 180=360 deg 3 players: 120=260 deg 4 players: 90 deg 6 players: 60 deg *8 players: 45 deg

30 deg is for 12 players, but can be used in other ways, as well as other possibilities. (part of map has some kind of symmetry, other parts aren't the same.)

I like 8-players maps. Then I can play for a loooong time with the AI and like the game (I don't like short games).

Don't forget that we don't have only rotations. We can use translations and symmetries to create fair 8-player maps.

combinations i think of could be:

2-player : translations , rotation of 180° , symmetry

3-player : translations , rotation of 120°

4-player : translations , two symmetries (or rotations of 90° which need to be fixed before)

5-player : translations (or rotations of 72° which need to be fixed before)

6-player : translations , rotations of 60° , symmetry + rotations of 120°

7-player : translations (or rotations if fixed ...)

8-player : translations , combinations of symmetries and translations , rotation of 180° and translations, or 2 symmetries and a rotation of 60° (or rotations of 45° if fixed)


Top Quote
einstein13
Avatar
Joined: 2013-07-29, 00:01
Posts: 1118
Ranking
One Elder of Players
Location: Poland
Posted at: 2015-01-29, 10:32

gnarfk wrote:

einstein13 wrote:

I had another- easier one - idea to do that. Steps to rotate:

  1. User: choose some points on the border of rotated land
  2. ? User: write the shape of the land (or: stright lines between the points? )
  3. Computer: Calculate the points posistions from point 1. and approximate it to map net
  4. Computer: Fill in the fields by specific type of terrain. Fields taken from inside the new shape taken from new points positions.

are you sure that your new shape will have the same number of edges ? i think it is the most important . and i don't think it will be easy to have this.

No, I'm not sure about this, but I have to test it first.

Don't forget that we don't have only rotations. We can use translations and symmetries to create fair 8-player maps.

combinations i think of could be:

2-player : (...)

I know that it is important to have symmetries, but for me fixing rotations is much more complicated. Symmetries are quite easy to implement... I guess face-smile.png

Maybe not every, but if we know how to do rotations- symmetries will be much more easier to do face-wink.png

Translations is adding a vector- I can do it now, without thinking:

vector translatedVector(basicVector, translationVector){
    newVector={0,0}
    newVector[0]=basicVector[0]+translationVector[0]
    newVector[1]=basicVector[1]+translationVector[1]
    return(newVector)
    }

It is basing adding face-smile.png


einstein13
calculations & maps packages: http://wuatek.no-ip.org/~rak/widelands/
backup website files: http://kartezjusz.ddns.net/upload/widelands/

Top Quote
gnarfk
Avatar
Topic Opener
Joined: 2015-01-05, 16:18
Posts: 70
Ranking
Likes to be here
Location: France
Posted at: 2015-01-29, 12:44

i know that symmetries and translations are very easy.

The point of what i said is : maybe we don't need to fix these non-exact rotations . We could already have a useful tool to create multiplayer maps.


Top Quote
einstein13
Avatar
Joined: 2013-07-29, 00:01
Posts: 1118
Ranking
One Elder of Players
Location: Poland
Posted at: 2015-02-02, 09:17

Gnarfk? I have "simple" problem (to this topic!):

I have list of points, also I can easily have list of lines. This list creates a figure, shape. Then I pick one (random) point. How can I test if the point is inside the shape or outside?

Please consider two cases:

  • The shape is a convex set
  • The shape isn't a convex set (should we split it into triangles to have convex set? But what should be the formula for that?)

Of course the set has no "holes" inside, so it is... (can't remember the correct word for that face-sad.png )


einstein13
calculations & maps packages: http://wuatek.no-ip.org/~rak/widelands/
backup website files: http://kartezjusz.ddns.net/upload/widelands/

Top Quote
gnarfk
Avatar
Topic Opener
Joined: 2015-01-05, 16:18
Posts: 70
Ranking
Likes to be here
Location: France
Posted at: 2015-02-02, 10:20

The first idea i think of is to use the jordan's theorem.

Let P be a point outside (we can choose a point very far away, or the rotation center, or find something else like a point whoose coordinates are higher that all the corners of your shape) , and M the point which you want to check whether it is Inside or outside.

the line (PM) cuts the lines which delimit your shape a certain number n of times (it is easy to comput these , solve 1 equation for each lines of your shape , and i can think of some ideas to make sure these equations have 0 or 1 solution and not an infinite number which can be the case in some situations).

If this number n is pair, M is also outside your shape. if n is an odd number, M is Inside your shape.

Edited: 2015-02-02, 10:22

Top Quote
einstein13
Avatar
Joined: 2013-07-29, 00:01
Posts: 1118
Ranking
One Elder of Players
Location: Poland
Posted at: 2015-02-02, 12:02

that is easy one face-smile.png Now only solve one problem: how to count (or rather: notice) intersections? face-smile.png I have one possibility:

  1. Get the two lines equations (p_i -> p_i+1, p_out -> p_test)
  2. Solve the x or y (any) value of intersection point of those lines (if exists: condition a1!=a2)
  3. Check if x is in range of (x_i, x_i+1), where p_i and p_i+1 are points defining the loop
  4. If yes- we have intersection, no- the intersection is outside the line segment (is it the correct math word?)

This problem is quite complex for computing. Is there any easier way to calculate this?!

Why I ask those questions? the idea is to rotate whole shape (ex. square, triangle, complex shape), then find points inside the rotated shape. Then we will save the original shape (a bit approximated to zigzag plane) and -what is more important - save surface area face-smile.png (but one more operation is needed: small expansion by radius = 0.5 to each direciton)

Edited: 2015-02-02, 12:03

einstein13
calculations & maps packages: http://wuatek.no-ip.org/~rak/widelands/
backup website files: http://kartezjusz.ddns.net/upload/widelands/

Top Quote
gnarfk
Avatar
Topic Opener
Joined: 2015-01-05, 16:18
Posts: 70
Ranking
Likes to be here
Location: France
Posted at: 2015-02-02, 12:52

i understand your idea. This could be a way to solve rotation problems. (we would need to fix things like "amount of a ressource in a shape" or things like that)

now , here is how could be implemented this idea.

We would have shapes defined with a list a_1 a_2 .... a_n points (we define then a_(n+1) = a_1 to close the shape). (i want these coordinates to be algebric numbers , you will see after why, but this condition is not much a problem)

We want to know wheter a point P is Inside or outside this shape.

Let a_max the point of the list with the higher y-coordinate. Let M be a point of coordinates (x(a_max) ; y(a_max)+ Pi) . (then , coordinates of M aren't algebric, and this will make sure all equations will have 0 or 1 solution, we will never be in a problematic situation with (MP) line following exaclty a segment line of the shape)

the (MP) line has a cartesian equation ax + by +c = 0, obtained with scalar product , and a condition : x being between x(M) and x(P) and y being between y(M) and y(P). (EQUATION of (MP) )

each (a_i a_i+1) line has a cartesian equation a_i x + b_i y +c = 0, obtained with scalar product , and a condition : x being between x(a_i) and x(a_i+1) and y being between y(a_i) and y(a_i+1). (EQUATION of (a_i a_i+1) )

let c =0

For i from 1 to n do

solve system { EQUATION of (MP) & EQUATION of (a_i a_i+1) } and check if the solution matches the condition

if solution found then c+1 -> c

EndFor

if c is odd then YES else NO


Top Quote
gnarfk
Avatar
Topic Opener
Joined: 2015-01-05, 16:18
Posts: 70
Ranking
Likes to be here
Location: France
Posted at: 2015-02-02, 12:58

as the systems will always be of the same type , and as they have everytime a solution, we can even write directly the formula of the solution in the 'solving part' , and then check if the solution is where it should.

The computation of this would not be very hard for a computer . the number of operations being not too big. We can extend this algorithm to shapes with holes. (instead of a list of points, give directly the list of equations of all the border-lines with the ranges)

On the same principle we will have things that could work on shapes with holes, or shapes with non-linear equation (circles , ellipses, other ...) as long as these equations could be computed , and where the ranges are well defined.

Notice : if you can describe your shape as a Union of disks , it will be very easy to compute your problem : a point is in the shape if its distance from one af the disks centers is shorter than its radius. But here , the problem is to find these disks for any type of shape ...

Edited: 2015-02-02, 13:13

Top Quote
einstein13
Avatar
Joined: 2013-07-29, 00:01
Posts: 1118
Ranking
One Elder of Players
Location: Poland
Posted at: 2015-02-02, 13:30

Yea face-smile.png You've got my point! face-smile.png But the idea of using universal line equation (a x + b y + c =0) is better than mine (y = a x + b, with 2 special cases: when a = 0 OR a = +/- infinity).

The computation time (for all the map!) will be about:

  • n_x - x dimension of map
  • n_y - y dimension of map
  • m - number of points
  • T=O(n_x * n_y * m)

We can narrow n_x and n_y by getting n_x_min, n_x_max, n_y_min, n_y_max as a coordinates of ROTATED points:

  • a_i=(a_i_x, a_i_y) OR a_i[0]=a_i_x, a_i[1]=a_i_y if we use array instead of vector class
  • n_x_min=min(a_1_x, a_2_x, ... , a_n_x)
  • n_x_max=max(a_1_x, a_2_x, ... , a_n_x)
  • n_y_min=min(a_1_y , a_2_y, ... , a_n_y)
  • n_y_max=max(a_1_y, a_2_y, ... , a_n_y)

Then we can consider point P only inside the sqare ((n_x_min, n_x_max),(n_y_min, n_y_max)). -> range notation of square

But the most important point is that we should consider only ROTATED points face-smile.png (I know that it is easy to forget about it face-grin.png )


einstein13
calculations & maps packages: http://wuatek.no-ip.org/~rak/widelands/
backup website files: http://kartezjusz.ddns.net/upload/widelands/

Top Quote