I am creating a simple little 2d scroller which has the basics already created (basic physics/jumping/sprite movement/collision for outer screen+ground) but now I want a bit of help.




I know most of the logic and theory behind what I want to do, but I want to hear others opinions/takes on the problem trying to be solved.

Problem: Which is the best way to generate a complete level dynamically and randomly while maintaining some logical balance. Also the best way to do collision for the level.

My solution: Create an array



in size. This will give us the height in which to place tiles and the width of the entire level to generate. Next we will populate the array with a ground of ground tile 'G' in the bottom row of the array



Next we have to randomly generate platforms 'P' as well as in the future collectable items 'C'. The logic behind proper placement of platforms while being random confuses me as they also have to be logically placed. Platforms should not overlap while there should also be sufficient X and Y distance apart from them. They should also vary in level height as well as length. This is to say from 0 (game ceiling) to 14 (just above game floor) the height of the platform should be randomly placed, as well as randomly generate its length in the X direction. It should also check that it is not cramped for space within it's generated location. So that platforms have some space apart in the X and Y axis, if this makes sense.

So I have to iterate through both X and Y tile positions with two loops placing the tiles in a random fashion while maintaining a logical order. The logical path finding algorithm that will need to be use eludes me and pseudo code or logic from you guys might help.

I believe it would need to work something like so:

1) Generate height to place the platform, as well as its length, at current X position
2) Check distance to other platforms from left of beginning to the right of ending as well as every tiles bottom and top in X direction. Should also check diagonals from beginning and ending of platforms
3) If the platform fits place it
4) Scroll forward platform X length in the array + random to find a new starting point for a platform

Afterwards you can iterate the array again looking for platform 'P' cells and calculate the tile above them to place random collectables 'C' cells.

Once done you can use this level array and iterate it every frame of the game drawing the tile map to the screen since each tile in the array is a physical position within the game screen. Or draw entire level at once if memory permits (which it should because each tile is not a new image, it is a pointer to a slice of the main image).

So: has anyone done anything similar or can offer up some better ways to attempt this. Or some pseudo code with the main logic behind such a algorithm?

Also this doesn't even solve for collision checking. You need to create another algorithm that calculates which cells the four corners of the player sprite are located and check for the tile. if it is 'G' or 'P' (ground or platform) tiles it should cause a collision flag and the game logic will handle from there, else if it is a 'C' flag, remove the tile and increase game points and so forth. The problem is that you only know the pixel positions for the corners of the sprite, so you would have to translate them into tile positions in the array with a bit of math.

Anyways yea. If anyone wants to see the code I can provide them what I have so far, although it isn't necessary for providing pseudo logic. I haven't refactored it yet and requires the PSPSDK to be installed as well as a SDK wrapping library, and a PSP to test on.

This post was edited by AbDuCt on Oct 16 2014 06:38pm

if I were to do it I would define a set of possible platforms you could make and along with them define constraints on what's the minimum distance in each direction that these platforms need to be from other obstructions. maybe have different classes of platforms that need to be treated differently. I think that that if you try and go about it truly randomly you'll end up with a ton of really strange map configurations.

Instead of iterating over the map each time just store an array of existing objects, and an array of possible positions you can place a new object. When you select a position for this object, apply its constraints to generate the invalid positions and remove them from this list. This way every time you go to add an object to the world, you dont have to search for a new position because your list is autoupdated just by adding an object.

You have any pseudo code for this or a more indepth explanations. It seems this might be something that could work.

So this is me typing directly into d2jsp, but something like this?



This post was edited by Minkomonster on Oct 16 2014 08:35pm

I see what you mean now. Unfortunately it may be a bit tricky to do in C.

You're essentially saying keep a list of all good spots and then mark them as bad as you place platforms. The only downside I can see to this is the lack of being able to specify platform type. It still also doesn't make the collision detection any easier.



I could do this, but it wouldn't really change anything. The logic of seeing if the blocks are free is still there and the only thing it removes is the generating of the platform rules, which may or may not be a bad thing. I could possibly create a platform structure which holds generic rules for different size platforms and with this randomly select between them to place them. It still revolves around the main part of iterating to find empty tiles.


I guess there isn't a really easy way to go through with this. I may take a look at ascii rpg games that are open source and see how they generate their maps. I saw one a while back that used the array method and placed symbols for doors and walls and corridors and such and had all the rules to check if placement was valid. I think I ported a C version to C# or something for unity a while back. I'll have to look.

Edit:: found it:

http://pastebin.com/FBZ1Ua0w

This post was edited by AbDuCt on Oct 16 2014 09:41pm