iDevGames Forums
2D map storage structures - Printable Version

+- iDevGames Forums (http://www.idevgames.com/forums)
+-- Forum: Development Zone (/forum-3.html)
+--- Forum: Game Programming Fundamentals (/forum-7.html)
+--- Thread: 2D map storage structures (/thread-5405.html)



2D map storage structures - SOUR-Monkey - Jun 16, 2005 02:59 AM

I am going to make a 2D top-down racing game, but I'm not sure how I want to deal with levels.

I want to be able to have fairly large levels (you won't be able to see it all at once, they are pretty long) with roads that curve smoothly around corners. I'd like to be able to make the actual level content varied as well, so that you don't see the exact same buildings flashing past every second but rather see a little variation in there. And I'd like to be able to keep the number of textures as low as possible.

Now, I know that adding variation will increase the number of textures required but that is not something I'm too concerned about. The thing I'm worried about is how to efficiently store the levels and still keep it easy for someone to create them.

If I construct the level out of a series of equally-sized squares then it becomes very difficult to have each corner different, as I will have to use the same (or one of a few) textures for each corner and therefore each corner will have the same shape and size. The level designer will have to make lots and lots and lots of different tiles if they want lots of different corners, which is time consuming for them and memory consuming for the computer.

Alternatively, I could have a set of tiles (i.e. a tile for the edge of the road) which can be placed anywhere on the map with any transformation. This would make it easy to keep the number of tiles required low, although the level would turn into a birds-nest of polygons. Unfortunately, curves would no longer be smooth if I did that, and tiles would overlap which would make them look very weird (imagine two rectangles with lines running across them joining each other at different angles).

Another approach is to have a series of tiles for things like trees and buildings which don't occur too often and are fairly similar. Roads would be specified using a series of tiles, one for the road edge, one for the road surface, one for the center etc. The person making the level could then draw a curve defining the road's shape, and the level editor would automatically work out a series of quads to draw the road smoothly with. That is getting pretty complicated though, especially when I start adding things like control points to change the width of the road at a specific point.

I think that the curve idea is the best for ease of use and achieving the overall goal, but it's the worst to program into the game. So - if anyone has any useful advice, I'd love to hear it. I've never done anything like this before, and I have to say I'm a little lost :-p


2D map storage structures - TomorrowPlusX - Jun 16, 2005 04:23 AM

Personally, I'd not use tiles. I'd use a road description as a bezier curve, which I'd subdivide into short segments, and then draw as quads ( provided the segments are short enough, it'd look like a smooth curve ). The buildings and whatnot would be random -- e.g., a box with random height/width/depth and random texture ( of a set of building textures ) and so on.

Your whole level could exist entirely of a random seed value and a bezier path.


2D map storage structures - SOUR-Monkey - Jun 16, 2005 09:15 PM

I don't intend to randomly generate levels, although that could be an option. It does seem like the best option (for usability, not programming) is to use some sort of spline to define the road, but like I said that's gonna be pretty hard to program.

I'll take a look into it today.


2D map storage structures - OneSadCookie - Jun 16, 2005 09:19 PM

bezier curves are remarkably easy. you should be pleasantly surprised Smile


2D map storage structures - NitroPye - Jun 17, 2005 04:09 AM

OneSadCookie Wrote:bezier curves are remarkably easy. you should be pleasantly surprised Smile
I am going to be honest, I have always avoided any kind of curves and even shuddered at the thought. If that is not sarcasm, well then thats a great sigh of relief.


2D map storage structures - OneSadCookie - Jun 17, 2005 04:17 AM

That's not sarcasm. Bezier curves really are remarkably easy. Other kinds of curves can quickly get very difficult, but fortunately Bezier is usually enough Smile


2D map storage structures - TomorrowPlusX - Jun 17, 2005 10:35 AM

Bezier itself is so easy you could implement it while falling down a flight of steps ( at least, recursive bezier subdivision is, quadratic is actually simpler but requires some math ). The issue is how you join the segments.

First, here's some bezier code I wrote -- YEARS ago -- which I posted on CocoaDev when somebody asked me for an implementation. It's primitive ( dating to my programming on BeOS in the late 90's and I didn't trust their implementation of the STL, so I made my own list types... because I was young and brash )

http://www.cocoadev.com/index.pl?BezierPathMathFunction

If you don't have *any* sharp turns, it will be straightforward. Say your road is of W width, then, for each point ( junciton between two line segments ) in your subdivided bezier path, you want to project a point W/2 units along the angle bisecting the junction, outwards and inwards. DO this for each junction, and then you have a set of points which you can use to draw quads.

For a higher quality approach, or for situations where you know you'll have sharp turns, you'll treat each segment as a quad ( projecting points perpendicularly from the segment ) and you'll make joining segments in between, perhaps as circles, or as triangles. If you do this, you'll have to handle the situation where the inn projected points of the segments overlap.

I realize now it's sounding scary, but seriously, aim high. You'll feel better, and learn a lot.


2D map storage structures - Dan Potter - Jun 17, 2005 12:12 PM

Here's another one, this one based on the idea of "seeding" the curve generator with points from your curve array, and then reading interpolated values between them.

http://www.allusion.net/svn/kos/kos/addons/libkosutils/bspline.c

I've used it to make long smooth tunnels in 3D space, so it probably would work for what you want.


2D map storage structures - TomorrowPlusX - Jun 17, 2005 02:23 PM

The bspline code is nice -- I also got my bezier and spline math from Ammeraal Wink


2D map storage structures - Dan Potter - Jun 17, 2005 04:27 PM

Thanks. Yeah, your math looked familiar to me. Grin That's a very cool book, and even now that half of what it covers is accelerated I find that it has useful stuff in it.


2D map storage structures - codemattic - Jun 18, 2005 12:23 AM

I use NSBezierPath to draw a path in my cocoa written editor - then -bezierPathByFlatteningPath to get a polyline which is exported to the game's level format.


2D map storage structures - codemattic - Jun 18, 2005 10:36 AM

TomorrowPlusX Wrote:First, here's some bezier code I wrote -- YEARS ago -- which I posted on CocoaDev when somebody asked me for an implementation. It's primitive ( dating to my programming on BeOS in the late 90's and I didn't trust their implementation of the STL, so I made my own list types... because I was young and brash )

http://www.cocoadev.com/index.pl?BezierPathMathFunction

in your article you write:
TomorrowPlusX Wrote:If you're interested in calculating the actual intersection points of arbitrary paths, I have some code that will do that too...
could you post that intersection finding code - it would be really useful!