Jump to content

  • Log In with Google      Sign In   
  • Create Account

How do I simplify the symmetry math


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
7 replies to this topic

#1 DareDeveloper   GDNet+   -  Reputation: 956

Like
0Likes
Like

Posted 11 May 2014 - 02:13 AM

Hi all,

 

I did not have to deal with math for a very long time. Now I have a hard time finding an elegant solution for the following problem:

 

When I build a map procedurally, there is a mechanism that makes sure all the work is done only once for each mirrored pixel.

A method forEachPixelToUpdate(streamSource, scope, action, map, mirrorMode, mirrorLine) can be used for that.

 

The actions that modify the map on a pixel basis can work with the following parameters

action.apply(scope, [ streamSource, map, indexX, indexY,
                    mirrorIndexX, mirrorIndexY, maxValue, minValue,
                    neighborTopLeft, neighborTopCenter, neighborTopRight,
                    neighborLeft, neighborRight, neighborBottomLeft,
                    neighborBottomCenter, neighborBottomRight ]);

Now the implementation of forEachPixelToUpdate is not quite correct.

The mechanism that determines if a position indexX / indexY is in the mirrored area for point symmetry is causing headaches.

 

Basically I draw a line through the map and want to continue with the next map row as soon as the line is reached.

 

The line is created from a pseudo random mirrorLine number that lies between 0 and (maxIndexX + maxIndexY).

    var line = new Object();
    if (mirrorLine > maxIndexY) {
        var offsetX = mirrorLine - maxIndexY;
        line.point1X = offsetX;
        line.point1Y = 0;
        line.point2X = maxIndexX - offsetX;
        line.point2Y = maxIndexY;
    } else {
        line.point1X = 0;
        line.point1Y = mirrorLine;
        line.point2X = maxIndexX;
        line.point2Y = maxIndexY - mirrorLine;
    }

I continue in the special cases that:

  • indexY is smaller than both line.point1Y and line.point2Y
  • or indexX is smaller than both line.point1X and line.point2X

For the other cases all I could think of was implementing complete linear function check implementations for both cases:

  • point1X = 0 (The line crosses the left and right sides)
  • point1Y = 0 (The line crosses the top and bottom sides)

At that point I got the feeling that the algorithm was getting too complex. There are probably implicit facts that can be used to simplify it.

If there are none, then probably using vectors and determining which side the index is on will probably be simpler than using a linear function.

I do not really know how to do either, though. I probably can, given enough time, but it is taking forever to make progress.

Any suggestions? This is the relevant code in forEachPixelToUpdate ()

    vertical: for (indexY = 0; indexY <= maxIndexY; indexY++) {

        if (MIRRORMODE_POINT == mirrorMode) {
            if ((indexY < line.point1Y) && (indexY < line.point2Y)) {
                continue;
            } else if (0 == line.point1Y) {

                // Linear function to determine if we are in the mirrored area
                var diff = line.pointX2 - line.pointX1;
                var slope = ?;
                var offset = ?; // ...

                // How do I do it?
            }
        }

        indexTop = indexY - 1;
        indexBottom = indexY + 1;
        if (0 > indexTop) {
            indexTop = maxIndexY;
        } else if (maxIndexY < indexBottom) {
            indexBottom = 0;
        }

        horizontal: for (indexX = 0; indexX <= maxIndexX; indexX++) {

            if (MIRRORMODE_AXIS == mirrorMode) {
                if (0 == mirrorLine) {
                    if (indexY > ((mapArray.length / 2) - 1)) {
                        break; // does break vertical work here?
                    } else {
                        mirrorIndexX = indexX;
                        mirrorIndexY = maxIndexY - indexY;
                    }
                } else if (1 == mirrorLine) {
                    if (indexX > ((mapArray[indexY].length / 2) - 1)) {
                        continue vertical;
                    } else {
                        mirrorIndexX = maxIndexX - indexX;
                        mirrorIndexY = indexY;
                    }
                } else if (2 == mirrorLine) {
                    if (indexX > indexY) {
                        continue vertical;
                    } else {
                        mirrorIndexX = indexY;
                        mirrorIndexY = indexX;
                    }
                } else if (3 == mirrorLine) {
                    if (indexX > ((mapArray.length - indexY) - 1)) {
                        continue vertical;
                    } else {
                        mirrorIndexX = maxIndexY - indexY;
                        mirrorIndexY = maxIndexX - indexX;
                    }
                }
            } else {
                if ((indexX < line.point1X) && (indexX < line.point2X)) {
                    continue horizontal;
                } else if (0 == line.point1X) {

                    // Linear function to determine if we are in the mirrored area
                    var diff = line.pointY2 - line.pointY1;
                    var slope = ?; // ...
                    var offset = ?; // ...

                    // How do I do it?
                }

                mirrorIndexX = maxIndexY - indexX;
                mirrorIndexY = maxIndexX - indexY;
            }

Edited by DareDeveloper, 11 May 2014 - 02:15 AM.

Given enough eyeballs, all mysteries are shallow.

ProcGames.com


Sponsor:

#2 DareDeveloper   GDNet+   -  Reputation: 956

Like
0Likes
Like

Posted 11 May 2014 - 05:54 AM

Damn, there seem to be so many things that are messed up.

 

I know I have a problem with rounding which I am not even sure can be fixed ...

and the dehaviour is extremely weird.

 

This implementation in the horizontal block does work in some cases ... a little, but the effect is mirrored and I do not get why it behaves the way it does when I try to continue the vertical loop (which would be more efficient). Guess I need to find many more problems before I can actually work on the thing I want to work on ...

    } else if (0 == line.point1Y) {
        // This block does not work ... figuring out how to calculate the offset in this case was too much. Maybe later ...
        // Linear function to determine if we are in the mirrored area
        var diff = line.point2X - line.point1X;
        var slope = (maxIndexX + 1) / diff;
        // var offset = ; // ...
    
        if (!logged) {
            log("diff: " + diff);
            log("slope: " + slope);
            // log("offset: " + offset);
            // log("comparison: " + indexY + " - " + ((slope * indexX) + offset));
            logged = true;
        }
    
    //    if (indexY > (slope * indexX + offset)) {
    //        continue vertical;
    //    }
    
    } else if (0 == line.point1X) {

        // This does something ... at least sometimes
        // Linear function to determine if we are in the mirrored area
        var diff = line.point2Y - line.point1Y;
        var slope = diff / (maxIndexY + 1);
        var offset = line.point1Y; // ...
    
        if (!logged && (indexX == maxIndexX / 2)) {
            log("diff: " + diff);
            log("slope: " + slope);
            log("offset: " + offset);
            log("comparison: " + indexY + " - " + ((slope * indexX) + offset));
            logged = true;
        }
    
        if (indexY > ((slope * indexX) + offset) + 1) {
            // log("Terminating at index X: " + indexX + " and Y: " + indexY + " with function value: " + ((slope * indexX) + offset));
            continue horizontal;
        }
    }

I also expected the logging to work every time ... indexX should be maxIndexX / 2 a few times but there is no logging, even in the successful cases.

I just do not know where to start with the debugging efforts ...

*Frustrated* sad.png

 

The whole thing currently looks like this:

ForeachTileHelper.prototype.forEachPixelToUpdate = function(streamSource,
        scope, action, map, mirrorMode, mirrorLine) {

    var mapArray = map.mapArray;

    var indexTop;
    var indexBottom;
    var indexLeft;
    var indexRight;

    var indexY;
    var indexX;
    var mirrorIndexX = 0;
    var mirrorIndexY = 0;

    var maxIndexX = mapArray[0].length - 1;
    var maxIndexY = mapArray.length - 1;

    var line = new Object();
    if (mirrorLine > maxIndexY) {
        var offsetX = mirrorLine - maxIndexY;
        line.point1X = offsetX;
        line.point1Y = 0;
        line.point2X = maxIndexX - offsetX;
        line.point2Y = maxIndexY;
    } else {
        line.point1X = 0;
        line.point1Y = mirrorLine;
        line.point2X = maxIndexX;
        line.point2Y = maxIndexY - mirrorLine;
    }
    log("mirror line (" + mirrorLine + ") from " + line.point1X + "/" + line.point1Y + " to " + line.point2X + "/" + line.point2Y);

    var logged = false;
    vertical: for (indexY = 0; indexY <= maxIndexY; indexY++) {

        if (MIRRORMODE_POINT == mirrorMode) {
            if ((indexY > line.point1Y) && (indexY > line.point2Y)) {
                continue vertical;
            }
        }

        indexTop = indexY - 1;
        indexBottom = indexY + 1;
        if (0 > indexTop) {
            indexTop = maxIndexY;
        } else if (maxIndexY < indexBottom) {
            indexBottom = 0;
        }

        horizontal: for (indexX = 0; indexX <= maxIndexX; indexX++) {

            if (MIRRORMODE_AXIS == mirrorMode) {

                if (0 == mirrorLine) {
                    if (indexY > ((mapArray.length / 2) - 1)) {
                        break vertical;
                    } else {
                        mirrorIndexX = indexX;
                        mirrorIndexY = maxIndexY - indexY;
                    }
                } else if (1 == mirrorLine) {
                    if (indexX > ((mapArray[indexY].length / 2) - 1)) {
                        continue vertical;
                    } else {
                        mirrorIndexX = maxIndexX - indexX;
                        mirrorIndexY = indexY;
                    }
                } else if (2 == mirrorLine) {
                    if (indexX > indexY) {
                        continue vertical;
                    } else {
                        mirrorIndexX = indexY;
                        mirrorIndexY = indexX;
                    }
                } else if (3 == mirrorLine) {
                    if (indexX > ((mapArray.length - indexY) - 1)) {
                        continue vertical;
                    } else {
                        mirrorIndexX = maxIndexY - indexY;
                        mirrorIndexY = maxIndexX - indexX;
                    }
                }

            } else {

                mirrorIndexX = maxIndexY - indexX;
                mirrorIndexY = maxIndexX - indexY;

                if ((indexX > line.point1X) && (indexX > line.point2X)) {

                    continue vertical;

                } else if (0 == line.point1Y) {

                    // Linear function to determine if we are in the mirrored area
                    var diff = line.point2X - line.point1X;
                    var slope = (maxIndexX + 1) / diff;
                    // var offset = ; // ...

                    if (!logged) {
                        log("diff: " + diff);
                        log("slope: " + slope);
                        // log("offset: " + offset);
                        // log("comparison: " + indexY + " - " + ((slope * indexX) + offset));
                        logged = true;
                    }

//                    if (indexY > (slope * indexX + offset)) {
//                        continue vertical;
//                    }

                } else if (0 == line.point1X) {

                    // Linear function to determine if we are in the mirrored area
                    var diff = line.point2Y - line.point1Y;
                    var slope = diff / (maxIndexY + 1);
                    var offset = line.point1Y; // ...

                    if (!logged && (indexX == maxIndexX / 2)) {
                        log("diff: " + diff);
                        log("slope: " + slope);
                        log("offset: " + offset);
                        log("comparison: " + indexY + " - " + ((slope * indexX) + offset));
                        logged = true;
                    }

                    if (indexY > ((slope * indexX) + offset) + 1) {
                        // log("Terminating at index X: " + indexX + " and Y: " + indexY + " with function value: " + ((slope * indexX) + offset));
                        continue horizontal;
                    }
                }
            }

            indexLeft = indexX - 1;
            indexRight = indexX + 1;
            if (0 > indexLeft) {
                indexLeft = maxIndexX;
            } else if (maxIndexY < indexRight) {
                indexRight = 0;
            }

            var neighborTopLeft = mapArray[indexTop][indexLeft];
            var neighborTopCenter = mapArray[indexTop][indexX];
            var neighborTopRight = mapArray[indexTop][indexRight];
            var neighborLeft = mapArray[indexY][indexLeft];
            var neighborRight = mapArray[indexY][indexRight];
            var neighborBottomLeft = mapArray[indexBottom][indexLeft];
            var neighborBottomCenter = mapArray[indexBottom][indexX];
            var neighborBottomRight = mapArray[indexBottom][indexRight];

            var maxValue = this.getBoundValue(true, map, indexX, indexY,
                    neighborTopLeft, neighborTopCenter, neighborTopRight,
                    neighborLeft, neighborRight, neighborBottomLeft,
                    neighborBottomCenter, neighborBottomRight);
            var minValue = this.getBoundValue(false, map, indexX, indexY,
                    neighborTopLeft, neighborTopCenter, neighborTopRight,
                    neighborLeft, neighborRight, neighborBottomLeft,
                    neighborBottomCenter, neighborBottomRight);

            action.apply(scope, [ streamSource, map, indexX, indexY,
                    mirrorIndexX, mirrorIndexY, maxValue, minValue,
                    neighborTopLeft, neighborTopCenter, neighborTopRight,
                    neighborLeft, neighborRight, neighborBottomLeft,
                    neighborBottomCenter, neighborBottomRight ]);
        }
    }
};

Edited by DareDeveloper, 11 May 2014 - 06:00 AM.

Given enough eyeballs, all mysteries are shallow.

ProcGames.com


#3 DareDeveloper   GDNet+   -  Reputation: 956

Like
0Likes
Like

Posted 11 May 2014 - 11:46 AM

Okay, after refactoring a little I found out what 2 of my problems are:

  • The fact that the coordinate system has point 0, 0 at the bottom while the map index 0, 0 is in the top left corner ... I did not get that right
  • I continued in the next line too often every time the y index was bigger than the function value). If there is a negative slope, I need to skip the first x indices and deal with the later ones, though
  • Oh yeah, and after rounding (indexX == maxIndexX / 2) the logging works

Still a lot to figure out ... and fixing those things is hard as well ...

 

Here is what I have so far:

 

https://github.com/AndyThiel/raidaces/blob/branch_0_0_2/src/main/webapp/js/modules/pcg/foreach_tile_helper.js

https://github.com/AndyThiel/raidaces/blob/branch_0_0_2/src/main/webapp/js/modules/pcg/mirror_mode_helper.js

 

EDT:

 

Another thing that makes things more complicated:

The problem with the seams might not always be related to rounding.

I noticed that mirroring along the diagonals is a special case, because the points get mirrored onto the same line.

Have not thought that through completely, but the isPointMirrored implementation might need to do something similar for points on the seam.


Edited by DareDeveloper, 11 May 2014 - 02:40 PM.

Given enough eyeballs, all mysteries are shallow.

ProcGames.com


#4 Vortez   Crossbones+   -  Reputation: 2698

Like
1Likes
Like

Posted 11 May 2014 - 02:18 PM

Im pretty sure this could be easily solve (and simplified) using vectors and matrices, no? Wish i could help you more but im having a hard time visualising what you're trying to do, and i never touched java script. One thing i noticed is the neightborgxxxxxx variables, i guess it would be nice if you could access them in a loop, and pass them as a structure, to shorten the code size at least.


Edited by Vortez, 11 May 2014 - 02:30 PM.


#5 DareDeveloper   GDNet+   -  Reputation: 956

Like
0Likes
Like

Posted 11 May 2014 - 02:48 PM

Thought about creating data containers to reduce the amount of params for the action functions.

I guess what stopped me so far is that I could not think of good ways to group the parameters.

 

Yes, maybe vectors are the way to go, but there is still the problem with the corners (0,0 as top left or bottom left) ... and I have a lot less experience there.

I have seen code that checked which side a point is on exactly once. That was when I did some research on Voronoi diagrams. I do not know how to dig that resource up.

It would also feel like getting sidetracked in a very unhealthy way. There must be a better time to look into that approach.

 

I have a lazy solution which kind of works. It uses only the lines that are used for axis symmetry. A little limiting, but I can live with that once I fix the remaining errors there ...


Edited by DareDeveloper, 11 May 2014 - 02:48 PM.

Given enough eyeballs, all mysteries are shallow.

ProcGames.com


#6 Vortez   Crossbones+   -  Reputation: 2698

Like
0Likes
Like

Posted 11 May 2014 - 03:04 PM

Could you post some screenshots of what you're trying to do? Im having trouble visualising the problem here.


Edited by Vortez, 11 May 2014 - 03:04 PM.


#7 DareDeveloper   GDNet+   -  Reputation: 956

Like
0Likes
Like

Posted 11 May 2014 - 03:52 PM

Well, the resulting map can be seen here (the small overview map):
 
http://procgames.com/raidaces/
 

When I started the thread I was hoping that the only problem with the code was that there was unneccessary complexity ... now I get that data structures are not optimal and the algorithm confusing. I should probably try to work on clarity ... because I am confused enough that I can not explain the problem.

There is a blur of causes and symptoms now that I do not really want anybody else to struggle with.

I still think the only problems lie in the forEachPixelToUpdate method and the methods of the MirrorModeHelper. Some points are handled twice, some not at all.

I think that indicates that MirrorModeHelper.prototype.isPointMirrored might cause all my troubles but not sure.

 

I don't think anybody should still look at the code and figure out what is wrong with it. Pointers to how this could be accomplished in a different way would be great, though (and if anybody can think of ways to improve the clarity ... please shoot :-)).

 

Don't really know where to start explaining, but the map is built as follows:

  • The kind of symmetry is chosen (axis or point, plus a line that divides the map in two parts - one that gets rendered explicitly, one that gets rendered because the values are copied there).
  • The map creators can use forEachPixelToUpdate to modify the map array. The function iterates over the points of one of those parts and passes the y and x indices and the mirror indices to the action that was passed to the forEachPixelToUpdate process.
  • First, all the points are set to 2 (the central layer) by using forEachPixelToUpdate and passing the action:
    ForeachTileHelper.prototype.setMiddleValue = function(streamSource,
            map, indexX, indexY, mirrorIndexX, mirrorIndexY, maxValue, minValue,
            neighborTopLeft, neighborTopCenter, neighborTopRight, neighborLeft,
            neighborRight, neighborBottomLeft, neighborBottomCenter,
            neighborBottomRight) {
    
        map.mapArray[indexY][indexX] = 2;
        map.mapArray[mirrorIndexY][mirrorIndexX] = 2;
    };
  • Then it is used again to raise and lower some of the values ... by calling it several times with the function created by this method:
    CreatorMapMoba.prototype.createCheckedRaiseAndLowerAction = function(doRaise,
            raiseLowerMap) {
    
        return function(streamSource, map, indexX, indexY, mirrorIndexX,
                mirrorIndexY, maxValue, minValue, neighborTopLeft,
                neighborTopCenter, neighborTopRight, neighborLeft, neighborRight,
                neighborBottomLeft, neighborBottomCenter, neighborBottomRight) {
    
            var currentValue = map.mapArray[indexY][indexX];
            if (1 == raiseLowerMap.mapArray[indexY][indexX]) {
                if (doRaise) {
                    map.mapArray[indexY][indexX] = currentValue + 1;
                    map.mapArray[mirrorIndexY][mirrorIndexX] = currentValue + 1;
                } else {
                    map.mapArray[indexY][indexX] = currentValue - 1;
                    map.mapArray[mirrorIndexY][mirrorIndexX] = currentValue - 1;
                }
            }
        };
    };

The raiseLowerMap has also been created in a similar way. First random pixels (0 or 1) were set:

ForeachTileHelper.prototype.chooseRandomBooleanValue = function(streamSource,
        map, indexX, indexY, mirrorIndexX, mirrorIndexY, maxValue, minValue,
        neighborTopLeft, neighborTopCenter, neighborTopRight, neighborLeft,
        neighborRight, neighborBottomLeft, neighborBottomCenter,
        neighborBottomRight) {

    var initialValue = (streamSource.consumeShort() % 2);
    map.mapArray[indexY][indexX] = initialValue;
    map.mapArray[mirrorIndexY][mirrorIndexX] = initialValue;
};

And then a cellular automation algorithm created areas out of the chaos.

ForeachTileHelper.prototype.basicCellularAutomationAction = function(
        streamSource, map, indexX, indexY, mirrorIndexX, mirrorIndexY,
        maxValue, minValue, neighborTopLeft, neighborTopCenter,
        neighborTopRight, neighborLeft, neighborRight, neighborBottomLeft,
        neighborBottomCenter, neighborBottomRight) {

    var mapArray = map.mapArray;
    var countNeighborsTrue = 0;

    if (1 == neighborTopLeft) {
        countNeighborsTrue++;
    }
    if (1 == neighborTopCenter) {
        countNeighborsTrue++;
    }
    if (1 == neighborTopRight) {
        countNeighborsTrue++;
    }
    if (1 == neighborLeft) {
        countNeighborsTrue++;
    }
    if (1 == neighborRight) {
        countNeighborsTrue++;
    }
    if (1 == neighborBottomLeft) {
        countNeighborsTrue++;
    }
    if (1 == neighborBottomCenter) {
        countNeighborsTrue++;
    }
    if (1 == neighborBottomRight) {
        countNeighborsTrue++;
    }

    // Guess I should update a buffer array first and keep using the original
    // for the algorithm.
    if (4 < countNeighborsTrue) {
        mapArray[indexY][indexX] = 1;
        mapArray[mirrorIndexY][mirrorIndexX] = 1;
    } else if ((3 < countNeighborsTrue) && (1 == mapArray[indexY][indexX])) {
        mapArray[indexY][indexX] = 1;
        mapArray[mirrorIndexY][mirrorIndexX] = 1;
    } else {
        mapArray[indexY][indexX] = 0;
        mapArray[mirrorIndexY][mirrorIndexX] = 0;
    }
};

Edited by DareDeveloper, 11 May 2014 - 04:09 PM.

Given enough eyeballs, all mysteries are shallow.

ProcGames.com


#8 DareDeveloper   GDNet+   -  Reputation: 956

Like
0Likes
Like

Posted 12 May 2014 - 02:32 PM

Dealt with the cartesian to img index brainf... by writing conversion methods (indexYToCartesian) and working with cartesian coords.
After a little break from the code I was also able to write the logic that determines the offset for points that are not on the y axis.

MirrorModeHelperPoint.prototype.calculateOffset = function(indexX, indexY, slope) {

	var offset = Math.floor(-1 * ((indexX * slope) - indexY));
	return offset;
};

 To simplify that I made sure that the first point of the line object (now created by getCartesianLine()) is the one on the left (lower x index).
 
I also separated the mirror mode helper logic for axis and point symmetry.
 
https://github.com/AndyThiel/raidaces/blob/branch_0_0_2/src/main/webapp/js/modules/pcg/mirror_mode_helper_point.js
 
Now the isPointMirrored check basically works. The seams are where I would expect them.
The remaining problems (still undefined or unsupported tile height values) might just be a result of rounding issues.
 
I made the problem visible at http://procgames.com/raidaces2/
 
There are colorful dots on the map (neon green for unsupported value, magenta for undefined value) and log messages show the coords of evil dots.

I guess some problems are not covered by that visualisation because when points are handled twice there is a chance that the resulting value is not outside the supported range.


Edited by DareDeveloper, 12 May 2014 - 02:38 PM.

Given enough eyeballs, all mysteries are shallow.

ProcGames.com





Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS