My Latest Distraction

Make games! Discuss those games here.

Moderators: Bob the Hamster, marionline, SDHawk

User avatar
Pepsi Ranger
Liquid Metal Slime
Posts: 1457
Joined: Thu Nov 22, 2007 6:25 am
Location: South Florida

My Latest Distraction

Post by Pepsi Ranger »

For several years I had an idea for a game that I thought would be awesome in 3D, and every so often I'd imagine what it would be like to make it. Knowing that I know nothing about 3D game design, or C++, or any of the tools I'd probably need to make it happen, I wasn't sure how I would see my vision come to life.

So, I started thinking about whether it was possible to do a 2D version on the OHR. For the longest time I couldn't think of a reasonable way to handle it.

Then something happened.

On Friday night, in rare form for me, I put my other projects aside, figured out a plan for this game that I had on my mind for several years, and immediately jumped into production. By the time the night was over I had the start of something functional. Two sessions later, I finalized the basic design for what you're about to see.

Behold, my latest distraction:

Image

What is that? Shroud?

Image

Part of the map unshrouded.

Image

The whole map unshrouded.

Image

Wait, wait, wait, wait, wait...is that a different map design? Could it be? No. Could it?! Is that...random map generation???

Image

Wait??? Is that random map generation for different sized maps? As many as five default sizes ranging from Micro to Mega (with Small, Medium, and Large in between)?

And does the map entrance randomly spawn at different locations?


Image

And what's with that cabin? What could that be about?

Image

Who would put a cabin by that lake?

Oh, well, maybe the random map generator put it there.


Image

Wait, now I must be pranking you. Where's the hero? You know I didn't just voluntarily move the camera to wherever the heck I wanted. Did I?

DID I???


What, oh what, is this game I'm making? The suspense must be unbearable.

Fortunately, the news will come often.

NOTE: If you're viewing this on April Fool's Day, be aware that the screenshots are backwards, and will hopefully return to normal on a day less cruel to new announcements.

NOTE 2: These jokes aren't funny, Mogri.
Place Obligatory Signature Here
User avatar
Mogri
Super Slime
Posts: 4668
Joined: Mon Oct 15, 2007 6:38 pm
Location: Austin, TX
Contact:

Post by Mogri »

I'm sorry; you're right. Reversing these screenshots has utterly and irrevocably ruined them.

Then again, you're the one making announcements on April Fool's Day.
User avatar
Pepsi Ranger
Liquid Metal Slime
Posts: 1457
Joined: Thu Nov 22, 2007 6:25 am
Location: South Florida

Post by Pepsi Ranger »

Then again, you're the one making announcements on April Fool's Day.
And that, folks, is the real comedy.
Place Obligatory Signature Here
User avatar
Meatballsub
Liquid Metal Slime
Posts: 996
Joined: Mon Oct 15, 2007 6:39 pm
Location: Northwest Georgia
Contact:

Post by Meatballsub »

This looks great. I'm looking forward to hearing more about it!
User avatar
sheamkennedy
Liquid Metal Slime
Posts: 1110
Joined: Mon Sep 16, 2013 9:29 pm
Location: Tama-shi, Tokyo, Japan
Contact:

Post by sheamkennedy »

Very awesome. It seems like the tiles are almost completely generated at random. I think it would be even more awesome if you attempted to make the tiles more procedurally generate. I'm not sure how you'd do this, but it would be neat if say: the lakes stayed with laketiles, the ground stayed with ground tiles, the streams stayed with stream tiles, the trees stayed with tree tiles. I think doing this would make the game appear to not be random even though it in fact is. Anyways this is really nice.
⊕ P E R S O N A L M U S I C: https://open.spotify.com/album/6fEo3fCm5C3XhtFRflfANr
� C O L L A B M U S I C: https://dustpuppets.bandcamp.com/releases
User avatar
Spoonweaver
Liquid Metal King Slime
Posts: 6462
Joined: Mon Dec 08, 2008 7:07 am
Contact:

Post by Spoonweaver »

sheamkennedy wrote:Very awesome. It seems like the tiles are almost completely generated at random. I think it would be even more awesome if you attempted to make the tiles more procedurally generate. I'm not sure how you'd do this, but it would be neat if say: the lakes stayed with laketiles, the ground stayed with ground tiles, the streams stayed with stream tiles, the trees stayed with tree tiles. I think doing this would make the game appear to not be random even though it in fact is. Anyways this is really nice.
Are we looking at the same pictures? I see all the things you're suggestion as taking place. Paths are even being made.
TMC
Metal King Slime
Posts: 4308
Joined: Sun Apr 10, 2011 9:19 am

Post by TMC »

More Pepsi Ranger madness. Neat to see quite a bit of variety in the map generation already.
sheamkennedy wrote:I'm not sure how you'd do this, but it would be neat if say: the lakes stayed with laketiles, the ground stayed with ground tiles, the streams stayed with stream tiles, the trees stayed with tree tiles.
I don't have any idea what you mean by that.
User avatar
Mogri
Super Slime
Posts: 4668
Joined: Mon Oct 15, 2007 6:38 pm
Location: Austin, TX
Contact:

Post by Mogri »

The lakes are shaped a bit oddly. What's your generation algorithm? I'd be inclined to do some cellular automata for lakes and maybe have a chance of generating some streams on top of that.
TMC
Metal King Slime
Posts: 4308
Joined: Sun Apr 10, 2011 9:19 am

Post by TMC »

It's a random walk with uniform chance of each direction. I suggested using a randomised floodfill.

If you used cellular automata would they have a depth state and mostly ensure smoothness?
User avatar
Mogri
Super Slime
Posts: 4668
Joined: Mon Oct 15, 2007 6:38 pm
Location: Austin, TX
Contact:

Post by Mogri »

TMC wrote:It's a random walk with uniform chance of each direction. I suggested using a randomised floodfill.

If you used cellular automata would they have a depth state and mostly ensure smoothness?
Take a look at this article. It's intended for caves, but would work just as well for lakes.
TMC
Metal King Slime
Posts: 4308
Joined: Sun Apr 10, 2011 9:19 am

Post by TMC »

Oh right. Very similar to image denoising using Potts models. Wonder if there are other uses of computer vision for mapgen...
User avatar
Pepsi Ranger
Liquid Metal Slime
Posts: 1457
Joined: Thu Nov 22, 2007 6:25 am
Location: South Florida

Post by Pepsi Ranger »

sheamkennedy wrote:Very awesome. It seems like the tiles are almost completely generated at random. I think it would be even more awesome if you attempted to make the tiles more procedurally generate. I'm not sure how you'd do this, but it would be neat if say: the lakes stayed with laketiles, the ground stayed with ground tiles, the streams stayed with stream tiles, the trees stayed with tree tiles. I think doing this would make the game appear to not be random even though it in fact is. Anyways this is really nice.
Well, this is sort of what the game does.

Each map is generated at the grass level first. Basically it picks from one of six grass tiles (with more likely in the future) and randomly sets them to Layer 0. It is flat terrain, no obstacles, and everything can be generated on top of it.

Then the engine sweeps the entire map using two for/do blocks and, based on five randomly generated variables (low volume, high volume, frequency, low mass, and high mass), will decide where the lakes go and how they should be formed. Lakes are assigned to Zone 1. I do this again with each successive land type: sandpits (Zone 2), forests (Zone 3), paths (Zone 4), rocks (Zone 5), and so on. The script knows not to lay certain zones on top of others. Paths, for example, are allowed on sandpits but not on the lake. Some zones have different assignments than others; the border rocks and the fence, for example, are randomly generated by location, but not so much by design.

The variables determine design as follows:

Low volume/high volume = The range that determines how many lakes or sandpits or forests or whatever will spawn on the map. A random number is picked between them. This is a maximum number and depends on whether or not the engine finishes sweeping the map before that number is exhausted. Every time a new lake zone or sand zone or whatever is started, it will decrease the pool of available lakes and such by 1.

Note: Every land type has its own generator, so lakes and sandpits will have separate volume numbers and separate everything else.

Frequency = How often the first tile to the zone will be placed on the map. Basically decides how close together each lake (or whatever) is to its neighbor. Lower numbers actually mean higher frequency, since it lays down the first tile if a certain number is called from that range. So, smaller ranges mean greater chances for having that number called. Forests have the lowest range (highest frequency) at 15 and rock zones (not the borders) have the highest range (lowest frequency) at 100. That means, for trees, there's a 1:15 chance that a new forest will be planted on that tile, whereas a rock field (called from a new sweep) will have a 1:100 chance of being planted on that tile.

Low mass/high mass = How large the lake, sandpit, forest, etc. will be. From the base tile, additional tiles will be drawn one at a time in random directions until the mass unit counter runs out. If the new tile overlaps a forbidden zone, it will go back a step, and try again. Again, the variables determine the range, and the actual number of tiles permitted to design it will fall somewhere in that range depending on what the random number generator draws.

Once the zones are set, a new script will sweep the map and fill in all the zones with the appropriate tiles (picking specific trees, rocks, etc. at random), which is why the map is allowed so much detail in spite of the hard-coded map being completely empty.

Finally, another script will seek out the edges of each zone and determine what shoreline, grass transition, etc. is needed to keep it from looking too sharp and angular.

So, it is most definitely procedural.
Mogri wrote:The lakes are shaped a bit oddly. What's your generation algorithm? I'd be inclined to do some cellular automata for lakes and maybe have a chance of generating some streams on top of that.
Once I get the first version released--shouldn't take too long to get something worth posting here--I'll be open to outside help in getting it to look nicer, and I'll be more than happy to share what I've got and take advice on how to improve it. As of now, I just want to get a foundation set so that I can determine whether this game is a good idea.

Which brings me to tonight's tidbit of information:

Image

Yep, you're looking at waypoints.

More specifically, waypoints of which the scripting has given me a serious headache.

Obviously, the red tiles won't be there in the final version--they're just there for now to help me bug test this sucker. But the goal is to allow the player to click on a random location on the map and send the hero walking there. How and for what reason, I'll explain in the next post (or one soon after).

This has been one of the hardest game design features I've encountered in any of my games because I'm not good with the idea of algorithms, and I'm pretty sure locating the best path between hero and red x will require something fancy. In the screenshot above, you'll see that the path is easily drawn when the x-y tile destination is fairly straightforward. Even at zone borders it can find a path to the x, as long as it doesn't have to think around corners. Once it has to change direction or think of a quicker path to the red x, things get complicated quickly, and I'm finding it very difficult to organize my thoughts on how to keep the pathfinding smart.

I'm now working on my third revision of the script for waypoints, and though I'm getting a better sense of how I should handle it, the execution is still a brain-fry. Right now I'm trying to think of it in terms of laying down checkpoints between the source and the destination and drawing paths between each one. This is probably the easiest way, but determining where those destination checkpoints should go is just as hard as navigating the field from beginning to end. Hence, my racked brain.

I'm hoping to think my way through this logically by the weekend. But this would certainly be a good time for you advanced plotscripters to sound off your ideas on what makes a good pathfinding algorithm. I'm sure it's better than what I'm working with, and if you've got an idea, I'll listen.

More to come soon.
Place Obligatory Signature Here
User avatar
Meatballsub
Liquid Metal Slime
Posts: 996
Joined: Mon Oct 15, 2007 6:39 pm
Location: Northwest Georgia
Contact:

Post by Meatballsub »

Pepsi Ranger wrote:But this would certainly be a good time for you advanced plotscripters to sound off your ideas on what makes a good pathfinding algorithm.
You say that as if your script thus far is mediocre. It's freaking amazing.

I'm trying to figure a basic random map generation script for a small part of my game, and have yet to wrap my head around the idea. The fact that you already have one working (and it works well), makes me very envious of you.
User avatar
Bob the Hamster
Lord of the Slimes
Posts: 7658
Joined: Tue Oct 16, 2007 2:34 pm
Location: Hamster Republic (Ontario Enclave)
Contact:

Post by Bob the Hamster »

Very cool, Pepsi!

When I first glanced at that screenshot I assumed that the park was afflicted by a Plague of Blood :)

The best algorithm for finding a path from one part of the map to another is called A-Star. I have never programmed A-Star pathfinding in plotscripting, but I know other people have.
User avatar
sotrain515
Red Slime
Posts: 59
Joined: Wed Dec 26, 2012 3:23 pm

Post by sotrain515 »

Bob the Hamster wrote:The best algorithm for finding a path from one part of the map to another is called A-Star. I have never programmed A-Star pathfinding in plotscripting, but I know other people have.
Yup, A*. Obligatory wiki link featuring neat animations and pseudo-code: http://en.wikipedia.org/wiki/A_star

I have A* pathing working in my game, but all my advice is strictly amateur. I'm self-taught I guess is what I'm saying.

The way mine works is to start with the x,y coordinates of the destination (in your case, where you have clicked) and then have the x,y coordinates of the searcher (in your case, your main dude). Next you radiate outward from the destination, assigning increasing values to each tile as you fan out, with obstructions being assigned no value. Do this until you've hit your dude or reached your maximum range.

For example, say you had the following map:

Code: Select all

[ ][ ][ ][ ][ ]
[ ][C][W][ ][ ]
[ ][ ][W][ ][ ]
[ ][ ][W][D][ ]
[ ][ ][ ][ ][ ]
C is where you've clicked, D is your dude and W's are walls (or badguys or lava pits or whatever; some type of obstruction).

First, assign a 1 to the C tile:

Code: Select all

[ ][ ][ ][ ][ ]
[ ][1][W][ ][ ]
[ ][ ][W][ ][ ]
[ ][ ][W][D][ ]
[ ][ ][ ][ ][ ]
Next, fan out from there with each neighboring non-obstructive tile being assigned a value of adjacent tile +1. Obstructive tiles are assigned zeroes:

Code: Select all

[ ][2][ ][ ][ ]
[2][1][0][ ][ ]
[ ][2][W][ ][ ]
[ ][ ][W][D][ ]
[ ][ ][ ][ ][ ]
Keep going 'til you've reached the dude (or a tile adjacent to the dude I suppose):

Code: Select all

[3][2][3][4][5]
[2][1][0][5][6]
[3][2][0][6][ ]
[4][3][0][D][ ]
[5][4][5][6][ ]
Next, tell your dude to move from highest tile-value to lowest (ignoring zeroes) until he reaches the tile valued at 1. You'll notice that he has two choices, north or south, that are both equally valuable. I pick randomly when that's the case, but it's probably easier to just always prefer one direction over others (i.e. start checking for the lowest tile with the northmost, then check east, then south, then west).

Now, as for how to implement this stuff in your actual code, well... Personally I do it iteratively rather than recursively. But then I was running into buffer overflows on mine (which featured monsters that could search the entire map).

As for where to store your map tile values, you have a few options: primarily zones, an invisible map layer and globals. If you aren't using all your layers and won't ever have a range of more than [whatever the map tile limit is... 256?], I'd suggest using a map layer. It makes testing much easier, since you can temporarily sub in a layer that draws "0", "1", "2", etc. over top of your map and you can basically watch the A* generation in action. Then when you're done testing, just replace the A* layer with a blank layer and it will become invisible to the player.


Okay, I took a look around and found the old thread about it, such as it was (started by me don't you know): http://www.slimesalad.com/forum/viewtopic.php?t=5514

Also, Mogri talks some about it in his Phantom Tactics thread here: http://www.slimesalad.com/forum/viewtop ... 5&start=90

I remember BMR had posted some very nice code examples of it, too, but I can't seem to find that anymore.
Post Reply