• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
DareDeveloper

How do I simplify the symmetry math

7 posts in this topic

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
0

Share this post


Link to post
Share on other sites

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
0

Share this post


Link to post
Share on other sites

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
0

Share this post


Link to post
Share on other sites

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
1

Share this post


Link to post
Share on other sites

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
0

Share this post


Link to post
Share on other sites

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

Edited by Vortez
0

Share this post


Link to post
Share on other sites

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
0

Share this post


Link to post
Share on other sites

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
0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0