Latest Posts

Topic: Completion of a map by symmetry

einstein13
Avatar
Joined: 2013-07-29, 00:01
Posts: 1089
Ranking
One Elder of Players
Location: Poland
Posted at: 2015-02-07, 19:23

Ok, I don't have much time, but I've done some work to test my solution face-smile.png It is not a text file, but some images included (to see how it works). Text will be in the future.

http://student.agh.edu.pl/~rak/widelands/files/RotationsOfMap/rotationsMathematica_1.02.pdf (direct link to PDF file)

http://student.agh.edu.pl/~rak/widelands/files/RotationsOfMap/rotationsMathematica_1.02.nb (if somebody has Wolfram Mathematica 10)

Some information:

  • File is ~10 MB of PDF, so be patient (or download to disk, then open)
  • I will test some more possibilites soon, but it will take some time (not only 2 shapes and 3 angles total)
  • The code is a bit messy, because I thought that Mathematica will handle with infinities, but it didn't
  • at the end I will test gnarfk's idea too (but it will take much more time: it is programistic-complex, but maybe less than mine)
Edited: 2015-02-07, 19:25

einstein13
calculations & maps packages: http://wuatek.no-ip.org/~rak/widelands/

Top Quote
gnarfk
Avatar
Joined: 2015-01-05, 16:18
Posts: 37
Ranking
Pry about Widelands
Location: France
Posted at: 2015-02-08, 10:12

I looked at your work. It allow us to see that the "shape transforming thing" is an interesting idea, that could work for any type of transformations.

But i don't like your "expanding" idea.

If we want to calculate terrain type in a shape , we don't need to expand. The shape is defined by a list of nodes , and the frontier is the edges. Then we have to see whether the center of each FIELD is Inside the shape or not. We don't need to expand the shape.

Don't forget that we calculate terrain type , which is an attribute of the field, not of the nodes.

If we calculate an attribute of the nodes, it is altitude (which can be interpolated from the ones of its closest neighbours), presence or not of bobs (we can put the image of the original bob in the closest node which hasn't already it), amount of ressources which has to be the same as the one of the original shape, and so has to be calculated in a way that ensure fairness between players (or calculated the same way i just proposed for bobs, adding the condition the node has to be compatible with this ressource)

another thing : when you choose your "outside point", it could be better to set its coordinates like (x_min - e , y_min - Pi) , because as Pi and e are not algebric and not algebrically dependant one another , all cases of lines being parallel will NEVER happen , and we won't need to think of these possibilities in the algorithm, the computation of the finding of the solution will be much easier.

Edited: 2015-02-08, 11:38

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

Ok, I guess that we have two different points of view to rotation aspect now.

My goal is to keep old shape for all the price. Then we can find solution for fillings (terrain type, bobs, trees, stone).

Your goal is to keep all the fillings as a major thing, then think about the shape.

The other solution is to think about compiling both ideas and create something even better. And to add something:

  1. In my idea the shape is not defined by list of nodes. It is defined by edges. I rotate edges, not all the nodes.
  2. Why expanding? Because If I don't expand, I will get points only INSIDE the shape which is defined also as a BORDER. I need to make "border"+"inside" to have whole basic shape. The size of expansion is between 0 and 1 point of length. It never expands to nodes different than the basic shape.
  3. To be specific, after several tousands of cases tested, I've found that expandin the shape by radius=0.35 of point is the best idea. How I know that? Because I've made a test:

The test:

  • Create example shape from several lines (69 nodes inside the shape)
  • Expand the shape by radius R
  • Rotate the shape by angle a (alpha)
  • Find the number of points inside the rotated shape
  • Compare with the basic number (69)
  • Do all the steps above for different R (0..0.5) and a (1..120 degrees)

Results:

  • For every R>0 and a=60*n the shape is perfectly correct
  • In 2/3~=67% cases of angles with radius R=0.35 the result number is at most 1 away from expected number (=69)
  • Other radiuses R has worse performance
  • The worst is - of course- R=0 and something above 0.5, what wasn't tested

You can disagree with the idea of rotations by using the shape, but It is working quite well with any angle.

Automated tests are awesome


einstein13
calculations & maps packages: http://wuatek.no-ip.org/~rak/widelands/

Top Quote
gnarfk
Avatar
Joined: 2015-01-05, 16:18
Posts: 37
Ranking
Pry about Widelands
Location: France
Posted at: 2015-02-08, 18:43

einstein13 wrote:

Ok, I guess that we have two different points of view to rotation aspect now.

i am not sure of that.

My goal is to keep old shape for all the price. Then we can find solution for fillings (terrain type, bobs, trees, stone).

i think my idea (consider terrain fields Inside the shape delimited by edges/nodes) keeps the old shape well enough.

Your goal is to keep all the fillings as a major thing, then think about the shape.

i also think about the shape , but i think "globally" and consider all aspects. i don't want to consider a rotation that allow us to start the job but doesn't allow us to finish it well

The other solution is to think about compiling both ideas and create something even better. And to add something:

  1. In my idea the shape is not defined by list of nodes. It is defined by edges. I rotate edges, not all the nodes.

if your shape is defined by a shape surrounded by segment lines, we only have to consider corner nodes, their image by the rotation (which are not systematically nodes but can create our equation list well enough)

  1. Why expanding? Because If I don't expand, I will get points only INSIDE the shape which is defined also as a BORDER. I need to make "border"+"inside" to have whole basic shape. The size of expansion is between 0 and 1 point of length. It never expands to nodes different than the basic shape.

i understand that, but if we consider that we want to fill our shape with a terrain type , using the nodes+edges as a frontier is an expansion of the shape defined by the centers of the fields which are Inside it ...

  1. To be specific, after several tousands of cases tested, I've found that expandin the shape by radius=0.35 of point is the best idea. How I know that? Because I've made a test:

Ok , you make a test that show that your way to expand your shape works with ONE EXAMPLE SHAPE and this radius. i read your algorithm, and i think (my instinct tells me, he may be wrong but he needs to see) that with another shape , the optimal radius won't be the same. (try a somewhat regularly convex shape, and then , try a really not convex shape like a 12-branch star.... and look if the optimal radii are the same)

The test:

  • Create example shape from several lines (69 nodes inside the shape)

(see what i said before : to be perfect, this test needs several different shapes of different sizes ...)

  • Expand the shape by radius R
  • Rotate the shape by angle a (alpha)
  • Find the number of points inside the rotated shape
  • Compare with the basic number (69)
  • Do all the steps above for different R (0..0.5) and a (1..120 degrees)

instead of doing all steps , you know that the number of points inside grows when R grows. So you don't have to do it for all R, but try something like a dichotomy, that will allow this algorithm to run more quickly, and maybe to find a better precision ....

You don't have to go from 1 to 120°, 1 to 30° is enough. (30 to 60 is symmetrical to this , and 60 to 120 is a exact rotation that works well of the precedent ones ...)

Combining these two ideas, your algorithm becomes:

let min = 0 , max=1 (the range in which R has to be).

While (max-min) is greater than the wanted precision

Let R = (min+max)/2

try for all angles from 1 to 30 with the R radius, make the mean of all results.

If the mean is bigger than the expected value , set max = R , else , set min = R .

at the end , you will have a range [min ; max] of the size you want , and you know that the expected optimal radius is in it.

Results:

  • For every R>0 and a=60*n the shape is perfectly correct
  • In 2/3~=67% cases of angles with radius R=0.35 the result number is at most 1 away from expected number (=69)
  • Other radiuses R has worse performance
  • The worst is - of course- R=0 and something above 0.5, what wasn't tested

You can disagree with the idea of rotations by using the shape, but It is working quite well with any angle.

i don't disagree. I just think of some different ways to optimize it. (and i consider ALL GOALS , as much aesthetic ones and goals of fairness that i had first when created this topic)

Edited: 2015-02-08, 18:56

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

My goal is to keep old shape for all the price. Then we can find solution for fillings (terrain type, bobs, trees, stone).

i think my idea (consider terrain fields Inside the shape delimited by edges/nodes) keeps the old shape well enough.

I don't think so, but I will test it as soon as possible.

i also think about the shape , but i think "globally" and consider all aspects. i don't want to consider a rotation that allow us to start the job but doesn't allow us to finish it well

I did few maps so fat, so I know that most important for me is not bob or tree- it can be added very easily. Most of time I spend on creating map terrain types. So that my idea contains only terrain-type shape.

if your shape is defined by a shape surrounded by segment lines, we only have to consider corner nodes, their image by the rotation (which are not systematically nodes but can create our equation list well enough)

It does.

Ok , you make a test that show that your way to expand your shape works with ONE EXAMPLE SHAPE and this radius.

Yes, I don't have much time to make more tests now. I tested one complex shape to see what is done with strange shape. I also tested triangle and square to see if everything works fine and it was. But the radius was different, as I mentioned above. The radius was changing from 0.0 to 0.5. It wasn't changing continously, because I don't know how to do that face-tongue.png

i read your algorithm, and i think (my instinct tells me, he may be wrong but he needs to see) that with another shape , the optimal radius won't be the same.

It can be - I have to test anything else face-wink.png Just give me any shape defined by values of correct nodes and I will test it for you. It will take only few hours to see if it is going right.

instead of doing all steps , you know that the number of points inside grows when R grows. So you don't have to do it for all R, but try something like a dichotomy, that will allow this algorithm to run more quickly, and maybe to find a better precision ....

First thing I thought: My algorithm is not expanding basic number of nodes inside. And I wasn't right:

basic shape

The image shows test shape (black line). Blue points are the nodes inside this shape and the green ones are the nodes on the border (not taken to calculations as default). We need to expand a little (even 0.001) to see the "border points" inside the shape.

basic shape

The second image shows what happened with the nodes if we use radius R=0.35 of expansion. This expanded shape is another black-line loop. There are 2 additional points between loops taken as "inside the shape".

So you are right- it takes some more points if we expand to R=0.35. But for me it is acceptable. Maybe for you isn't?

You don't have to go from 1 to 120°, 1 to 30° is enough. (30 to 60 is symmetrical to this , and 60 to 120 is a exact rotation that works well of the precedent ones ...)

It isn't symmetrical. Because the shape is not symmetrical. I've checked that.

i don't disagree. I just think of some different ways to optimize it. (and i consider ALL GOALS , as much aesthetic ones and goals of fairness that i had first when created this topic)

Maybe you know that you aren't the first one who wants to create such a tool? face-smile.png I guess that this is the first time it is so advanced. You've broght some ideas, me too, maybe some other people are thinking about it too?

Also I think that fairness is mainly connected to terrain types, then to slopes (heights of nodes). Slopes can be forgotten if are in small range (f.e.: randomly created between 9 and 12 of height), because all types of buildings can be built then.

To be more specific I will show one, last image:

basic shape

The blue dots are on the border of not-expanded loop. They are counting to any expanded loops (even 0.001). The green ones are on the border of loop with R=0.5. For me it is a limit. We don't need those points at all. This is why I tested only R between 0.0 and 0.5. Testing more R limit will add additional points. Also to add one more thing: you mensioned that expanding will add nodes that we don't want. This picture shows that there are 4 additional points to the shape with R=0.5. Is it much?

And one more information:

Wolfram Mathematica is working with algebraic precision as default. If you keep numbers as 1/2, sqrt(5), pi or e it will keep the numbers. So that the calculations are exact and it takes lots of time for a computer to calculate everything. I've kept that, so it is impossible to have more precision. But if I use machine precision (floating point numbers), I can even use more digits after point. For me it is not needed here. 15 digits is enough for such calculations.


einstein13
calculations & maps packages: http://wuatek.no-ip.org/~rak/widelands/

Top Quote
gnarfk
Avatar
Joined: 2015-01-05, 16:18
Posts: 37
Ranking
Pry about Widelands
Location: France
Posted at: 2015-02-08, 21:58

einstein13 wrote:

i also think about the shape , but i think "globally" and consider all aspects. i don't want to consider a rotation that allow us to start the job but doesn't allow us to finish it well

I did few maps so fat, so I know that most important for me is not bob or tree- it can be added very easily. Most of time I spend on creating map terrain types. So that my idea contains only terrain-type shape.

You mean that you want a tool that makes the symmetry or rotation for terrain , and then do manually the rest ?

So you are right- it takes some more points if we expand to R=0.35. But for me it is acceptable. Maybe for you isn't?

well , as the goal was to have the same number of points ...

You don't have to go from 1 to 120°, 1 to 30° is enough. (30 to 60 is symmetrical to this , and 60 to 120 is a exact rotation that works well of the precedent ones ...)

It isn't symmetrical. Because the shape is not symmetrical. I've checked that.

Well , you're right , we still have to go from 1 to 60 °. (but not to 120)

For the expansion radius , i think the problem is the area of your shape. We have to expand the shape so as the global area of the shape is equal to the area of 2 field triangles for each node. ( you can check in your example if it is the case )

The first solution i see for this is what i already said : if the original shape is wideland-map-editor generated , we consider the edges as a frontier, and in the image we look if the center of the field is in the shape. The area of the shape is exactly the area of the fields we consider. (and , as you said you want a tool that works for terrain type, you should consider this idea)

The second solution is to calculate the value of the radius in order to have the good area ( 2 triangles for each node in your shape) without adding new nodes in your shape... (in that case , the 60° rotation you had first will not be exact any more) I don't see any simple and general algorithm that will allow us to calculate easily the radius ....


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

Well , you're right , we still have to go from 1 to 60 °. (but not to 120)

For my algorithm there is no difference between rotating in one step to 30° and to 90°. There is huge difference between rotating to 90° in one step and rotating to 60°, then additional rotating by 30°. The result is the same, but computing time is much longer.

But you're right: for test I need only 0...60°. I only wanted to see the result of shape for 90° rotation.

For the expansion radius , i think the problem is the area of your shape. We have to expand the shape so as the global area of the shape is equal to the area of 2 field triangles for each node. ( you can check in your example if it is the case )

Probably this is the soulution for any shape. Now I don't have any good idea how to easy compute area of the shape. Integrate is a bit too complex (long computation time?). Deviding the shape into another (known area) shapes will be a good idea, but hard to implement now. If you know how to do that, just tell me face-smile.png I don't need very precise calculations. I want to prove that your idea of "2 triangles area for node" is truth for my case.

The first solution i see for this is what i already said : if the original shape is wideland-map-editor generated , we consider the edges as a frontier, and in the image we look if the center of the field is in the shape. The area of the shape is exactly the area of the fields we consider. (and , as you said you want a tool that works for terrain type, you should consider this idea)

I don't understand this idea. Can you tell me what are the steps of computing the rotation? What do you do first? Then what? ...?

The second solution is to calculate the value of the radius in order to have the good area ( 2 triangles for each node in your shape) without adding new nodes in your shape... (in that case , the 60° rotation you had first will not be exact any more)

So that I didn't missed any node in expanded shape. My goal was to keep the basic shape for any rotation, so there can be small differences between user-defined shape and created (expanded) ones. In my model that exists.

I don't see any simple and general algorithm that will allow us to calculate easily the radius ....

If you can easily calculate the area value inside the shape- it will be very easy face-smile.png


einstein13
calculations & maps packages: http://wuatek.no-ip.org/~rak/widelands/

Top Quote
gnarfk
Avatar
Joined: 2015-01-05, 16:18
Posts: 37
Ranking
Pry about Widelands
Location: France
Posted at: 2015-02-09, 14:07

einstein13 wrote:

The first solution i see for this is what i already said : if the original shape is wideland-map-editor generated , we consider the edges as a frontier, and in the image we look if the center of the field is in the shape. The area of the shape is exactly the area of the fields we consider. (and , as you said you want a tool that works for terrain type, you should consider this idea)

I don't understand this idea. Can you tell me what are the steps of computing the rotation? What do you do first? Then what? ...?

in this picture, i represent with green points the nodes , blue lines the edges , red points the centers of the fields. http://s21.postimg.org/tyodvkd8n/nodesedgesfields.png

My idea is : we want to set the terrain type of the fields, and to do so , look whether the center of the field (red point) is or not in the shape , which is delimited originally by blue segment lines defined each by 2 green points.

The algorithm : Originally we have a set of fields (that we can represent by their centers) , created by the user of the map-editor as the original shape.

For each field in our shape , we look if their neighbours are still in the shape or not. if not , we add this frontier (blue line) as a border of the shape (in our equation list , or pair of point list (the two green points delimiting the blue segment line) ).

then , we rotate this shape (rotate equations of borders, or rotate pair of points delimiting border segments).

For each field, we then look whether its center is or not in our rotated shape .

This algorithm has some advantages :

  • shape is user defined in the editor.

  • the area of the shape is the one that should be , depending of the number of fields we have in it, and so, statistically keeps something close to the good number of fields in the rotation image (but not systematically the same number, we have to try it.)

  • this algorithm also works if our shape has holes or is in multiple parts

(If the number is not everytime the good one , we can also optimize this algorithm : for each field in the image, look the proportion of its area Inside the shape( for it , we can look if the field is close to a border, and then solve a pair of equations, or use some tricks that'll allow to calculate this area in an approximative way but somewhat precisely enough) . Then sort all fields by this proportion, and keep the fields with higher proportion , because then we can choose the right number of fields... )

I don't see any simple and general algorithm that will allow us to calculate easily the radius ....

If you can easily calculate the area value inside the shape- it will be very easy face-smile.png

Maybe we can use pick's theorem to calculate the area of the shape , if its corners are exact nodes . but we can't be sure to keep the number of points when expanding (we will add new points ...) , and so i prefer the other solution .

Edited: 2015-02-09, 14:12

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

(If the number is not everytime the good one , we can also optimize this algorithm : for each field in the image, look the proportion of its area Inside the shape( for it , we can look if the field is close to a border, and then solve a pair of equations, or use some tricks that'll allow to calculate this area in an approximative way but somewhat precisely enough) . Then sort all fields by this proportion, and keep the fields with higher proportion , because then we can choose the right number of fields... )

Sorry, but I don't get this point. You assume that after rotating you will have more fields than in original shape? Sometimes it happens, but sometimes not. What about that case? (Or maybe I didn't understand the idea at all?)

Maybe we can use pick's theorem to calculate the area of the shape , if its corners are exact nodes . but we can't be sure to keep the number of points when expanding (we will add new points ...) , and so i prefer the other solution .

The pick's theorem will be useful, but when I expand the shape and want to calculate the field- it is useless. Expanded shape is NEVER defined by nodes.

And to comment your idea (current understanding):

It is very interesting. face-smile.png I love testing and probably I will try this too. Maybe it will solve lots of problems? But please- GIVE ME SOME TIME face-grin.png (or maybe you should test something?) For sure this idea contains only 6 types of lines, none of them is vertical (y=ax+b, "a" is never infinitive).

Today I've found Julia programming language. It is quite simple and created for math (like Wolfram Mathematica). The main difference is that it is free. You can try it, if you don't know any languages. But probably you know something (the picture you've sent was created somehow).


einstein13
calculations & maps packages: http://wuatek.no-ip.org/~rak/widelands/

Top Quote
gnarfk
Avatar
Joined: 2015-01-05, 16:18
Posts: 37
Ranking
Pry about Widelands
Location: France
Posted at: 2015-02-09, 19:04

einstein13 wrote:

(If the number is not everytime the good one , we can also optimize this algorithm : for each field in the image, look the proportion of its area Inside the shape( for it , we can look if the field is close to a border, and then solve a pair of equations, or use some tricks that'll allow to calculate this area in an approximative way but somewhat precisely enough) . Then sort all fields by this proportion, and keep the fields with higher proportion , because then we can choose the right number of fields... )

Sorry, but I don't get this point. You assume that after rotating you will have more fields than in original shape? Sometimes it happens, but sometimes not. What about that case? (Or maybe I didn't understand the idea at all?)

i assume that i'm not sure that the result will be PERFECT so i think of a method to optimize it, but maybe we won't need this idea if the main idea works well enough. This is only an optimization idea that is maybe not useful .

Maybe we can use pick's theorem to calculate the area of the shape , if its corners are exact nodes . but we can't be sure to keep the number of points when expanding (we will add new points ...) , and so i prefer the other solution .

The pick's theorem will be useful, but when I expand the shape and want to calculate the field- it is useless. Expanded shape is NEVER defined by nodes.

i know. But with the area of the original shape (which is defined by nodes) , you can calculate what area amount you need to add to your shape to have the correct area. (the final shape will not follow nodes but that's not a problem , we only need this shape to have the good area)

The problem is that we need to find a way to add this area without adding new points ... and that is not the only problem we need to solve...

But i still prefer the other idea.

And to comment your idea (current understanding):

It is very interesting. face-smile.png I love testing and probably I will try this too. Maybe it will solve lots of problems? But please- GIVE ME SOME TIME face-grin.png (or maybe you should test something?) For sure this idea contains only 6 types of lines, none of them is vertical (y=ax+b, "a" is never infinitive).

Take your time face-smile.png we are not in a hurry.

in my idea we have only 6 types of lines , so the equations will be easy to write , i didn't think of this advantage ... as i thought that with cartesian equations and my "non-algebrical number trick" we would never have been in a "parallel" situation or things like that ...

(we still need this trick using non algebrical number to avoid parallel situation ...)

Today I've found Julia programming language. It is quite simple and created for math (like Wolfram Mathematica). The main difference is that it is free. You can try it, if you don't know any languages. But probably you know something (the picture you've sent was created somehow).

I'll look at this language. it will be interesting if we share the code in the same language ...

i know lot of programming languages....(and am not afraid at all to learn other ones) The one i used to create this picture is "algobox" , a language designed for young students to learn basic algorithmics ... when i want to create short algorithms it is very quick and easy. (as soon as we need to define functions , methods, this language is not powerful enough)

At the end , we will need to implement this feature in the map-editor , and we should consider choosing a language that could work for it.


Top Quote