Author Topic: Simon blogs  (Read 37691 times)

0 Members and 1 Guest are viewing this topic.

Offline Simon

  • Administrator
  • Posts: 2692
    • View Profile
    • Lix
Re: Simon blogs
« Reply #225 on: July 31, 2019, 12:14:48 pm »


Christmas tree problem

You have a fir tree and want to decorate it with christmas lights.



The fir tree's green bushy "surface" is cone-shaped, with a circular boundary at the bottom.



You also have n candles. These are about to be placed on the fir tree.

In reality, the candles would be connected by electrical cable, which would restrict the candles' distribution on the tree. Assume that the candles need no electricity, or that the cable between any two candles is arbitrarily long.



Task. Distribute the n candles on the fir tree such that the candles are nicely spaced apart from all other candles. You may place candles on the boundary.

Precisely: Given a distribution D of the candles, compute the minimum of all distances d(k, k') between all candles kk' of D. We call this minimum f(D). We want to maximize f. Thus, denote by M the supremum of the minimum distances of all distributions, M = sup { f(D) : D is a distribution }. Finally, find an arrangement of the candles D that attains f(D) = M. If no such arrangement exist, instead find a sequence (Di) of arrangements such that the sequence of minimums f(Di) converges to M.

In a variations of the christmas tree problem, you're encouraged to avoid the boundary, too. Then, for each distribution, don't merely compute the minimum of all candle-to-candle distances, but also the minimum of all candle-to-boundary distances, and use the minimum of these two minimums. Across all distributions, maximize this value.

Example. Given only one candle, put it anywhere you like. If you'd like to avoid the boundary, too, then put the lone candle at the top of the tree.

Example. Given two candles, even if distance to the boundary doesn't matter, the best distribution depends on the shape of the cone. If the cone is very tall and thin, put one candle at the top and one on the circular boundary at the bottom. Otherwise, if the cone is squat and low-risen, put both candles on opposite points of the boundary.

Example. If your christmas tree is not a tree at all, but rather the unbounded real line, you can space the candles arbitrarily far from each other. This is very nice.



Application. If your christmas tree is instead the space of all colors, and you have 8 Lix player colors, find a distribution of 8 colors such that no two colors look more similar than necessary. This is hard, especially if you, in addition, want to avoid black because black lixes looks too much like the boundary level background.

End. The christmas tree problem is really about abstract metric spaces, not christmas trees, but christmas trees inspired me to first think about this problem in detail. I don't know whether this problem is known by other names in mathematics. I don't know whether it's more common to avoid the boundary or not.

-- Simon
« Last Edit: July 31, 2019, 02:22:18 pm by Simon »

Offline namida

  • Administrator
  • Posts: 9207
    • View Profile
    • NeoLemmix Website
Re: Simon blogs
« Reply #226 on: July 31, 2019, 07:06:39 pm »
With regard to Lix specifically, which color tends to be the most visible? Perhaps every player should see their own lixes in that color?
My released level packs:
Lemmings Plus Series | Doomsday Lemmings

Offline Proxima

  • Posts: 3406
    • View Profile
Re: Simon blogs
« Reply #227 on: July 31, 2019, 09:39:14 pm »
I really don't think that's a good idea. Players tend to get attached to their favourite colours and want to keep playing as them :)

Offline ccexplore

  • Administrator
  • Posts: 4930
    • View Profile
Re: Simon blogs
« Reply #228 on: July 31, 2019, 10:08:57 pm »
To be clear, this is mostly a solved problem for Lix, correct?  Hard to imagine how you'd do better for 8 with rainbow + black & white.  Basically the 8 corners of the RGB-space cube.  Though I suppose it is interesting to wonder for the case where black is also treated as boundary to avoid, whether there may be other winning configurations not using the remaining corners of the cube.

Obviously, you can also consider making lixes look different by other attributes besides color, but given how small the sprites are, I suspect it'd be tricky to create other visual differentiators as clear as color would be.

Offline Simon

  • Administrator
  • Posts: 2692
    • View Profile
    • Lix
Re: Simon blogs
« Reply #229 on: August 06, 2019, 04:50:46 am »
With regard to Lix specifically, which color tends to be the most visible? Perhaps every player should see their own lixes in that color?

Lovely idea for future projects. It would also obviate GUI to pick color. Fewer choices. I took (Player A's color on A's machine is same as player A's color on B's machine) unquestioned from physical board games.

I draw local player's lixes on top of everybody else's. Often, that's exactly want we want. Downside: Lone enemy attackers are invisible in an own dense crowd. Although (automatic color choices, local player gets best color) would have same problem.

I really don't think that's a good idea. Players tend to get attached to their favourite colours and want to keep playing as them :)

Yeah, I believe I don't want (fixed color that each local player uses for themself) in Lix.

#1 reason: people really care about the color. Raymanni even wants extra colors (8 -> 12) and would be happy to keep the player limit at 8; then, extra colors would be completely irrelevant to physics.

#2 reason: People in voicechat refer to other players by color. Opponents' colors must be clearly visible.

#3 reason: The replay format identifies teams by color.

#2 and #3 would work with server-side (for each team, fix a color across all machines). But since some color has to be picked and transmitted anyway, we can let the people pick it, they love it.

To be clear, this is mostly a solved problem for Lix, correct?

Right, unless Raymanni wants extra colors. Mainly, I wanted to write about the abstract problem, less about Lix.

Quote
Hard to imagine how you'd do better for 8 with rainbow + black & white. Basically the 8 corners of the RGB-space cube.

Neither the 1-metric nor the 2-metric in the RGB cube agree with the human visibility metric. Red (255, 0, 0) and black (0, 0, 0) are 255 apart and are clearly distinguishable. Bright green (0, 255, 0) and bright cyan (0, 255, 255) are also 255 apart, but far less disginguishable than red and black.

Sorry for late answers! More on ccx's ideas later.

-- Simon
« Last Edit: August 06, 2019, 05:00:36 am by Simon »

Offline Simon

  • Administrator
  • Posts: 2692
    • View Profile
    • Lix
Re: Simon blogs
« Reply #230 on: September 08, 2019, 09:39:56 pm »
Quote from: ccx
given how small the sprites are, I suspect it'd be tricky to create other visual differentiators as clear as color would be.

Right. Glaring colors with different lightness are good and easy to implement. The main point of the post was to explain my reluctance to implement Raymanni's desire for more than 8 colors, because 12 colors are harder to christmas-tree-distribute than 8 colors are.



Many news

I'm a software engineer by profession now.

The project is firmware maintenance and development in C++ on Linux. The firmware runs on electrical rectifiers attached to solar panels. My team is 7 people, I get along really well, and occasionally troubleshoot their problems with git.

The job interview was more about Lix than about my formal studies.

After I defended the PhD thesis in September 2018, I spent until April 2019 bugfixing the thesis based on both professor's thorough findings. This was a tricky decision, I could have published immediately without penalty, but I wanted the thesis to be solid. I didn't look for a job much while debugging the thesis. That's why it took 10 months from defense to job. But it's all good now.

Akseli: I solved the Lasertank level 40, Down the Drain. It's really a Sokoban level. Years ago, I solved levels 1-39 and many past 40, but always got stuck on level Down the Drain.

-- Simon

Offline grams88

  • Posts: 428
  • Everyone is like a brother or sister
    • View Profile
Re: Simon blogs
« Reply #231 on: September 08, 2019, 10:42:11 pm »
Lix has opened many avenues for you, welldone on getting the job Simon. :thumbsup: I'm glad you are settling into the job well.

I remember in my younger days those (Lasertank) levels were quite difficult and I don't think I got too far but I must give it a try in the future as I'm getting quite good at those Sokoban games in my present days. I enjoyed making my own levels and having my brother try to complete them, it's a good little game which I recommend to any sokoban fans.

There was game I completed recently which was the (Lmarbles) game which is based on a game made a long time ago where you had to copy the order of the molecules to complete the level. In Lmarbles you just have to get the order of the colors by moving them around until you get the right design or order so to say.

(Chuck's challenge) was a really good game I thought and there was a lot of levels where you had to move boxes around like the Sokoban type levels and some of them would drive you crazy.

In regards to the color's in Lix, I would try to avoid any color that looks similar to any of the other colors that have been implemented. Maybe this could be an issue if you were to implement more colors. I remember in worms Armageddon the colors Cyan and green felt as if they were too similar but I wonder if that is more a isolated problem with myself rather than with others. Anyway your lix color looks more like blue so no worries in that regard. :)

Offline ccexplore

  • Administrator
  • Posts: 4930
    • View Profile
Re: Simon blogs
« Reply #232 on: September 09, 2019, 02:12:33 pm »
Right. Glaring colors with different lightness are good and easy to implement. The main point of the post was to explain my reluctance to implement Raymanni's desire for more than 8 colors, because 12 colors are harder to christmas-tree-distribute than 8 colors are.

This is a stab at what one might do for 12 colors, excluding black as a color:


Some colors are not quite so distinct compared to the current 8, but I think above might still be manageable for most people?

That being said, how likely anyway are we to ever get a game using all 12 at once? :-\

Offline namida

  • Administrator
  • Posts: 9207
    • View Profile
    • NeoLemmix Website
Re: Simon blogs
« Reply #233 on: September 09, 2019, 06:14:14 pm »
My concerns there would be brown vs orange, purple vs pink, and white vs grey. Those easily could look like different shades of each other, especially in a situation where there aren't lixes of both colors near each other. I think the rest are distinct enough that they'd be recognizable as outright different colors even when not right next to each other. A darker shade of grey would probably resolve the issue in that case, though I think the other two pairs would likely be hard to redeem without instead making them too close to a different color. This still adds two more colors, though.
My released level packs:
Lemmings Plus Series | Doomsday Lemmings

Offline grams88

  • Posts: 428
  • Everyone is like a brother or sister
    • View Profile
Re: Simon blogs
« Reply #234 on: September 11, 2019, 11:08:52 pm »
Would 12 players not make the game a bit crazy and very hard to organise but if it is something you want to do go for gold. :)