It is currently Fri Dec 06, 2013 5:50 am

 All times are UTC

 Page 1 of 1 [ 17 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: A procedurally generated 2D "mesh" worldPosted: Tue Jul 12, 2011 3:08 am
 Harmlessness does no harm

Joined: Tue Sep 14, 2004 8:37 pm
Posts: 3913
Location: Ferriday, LA, US
Hey folks, I'm sticking my big toe back into the piranha-infested waters of game programming.

So, I want to try and build a game world that consists of polygonal shapes. Procedurally generated polygonal shapes, to be more accurate. I got the idea to add some spice to the old Roguelike system of using tiles or symbols for map layout by using irregular shapes, so there could be areas with rough, cavernous walls, serpentine streams, and so on.

I am starting off with a 2D "mesh" of sorts, basically just a set of points that make a square (although the starting shape is probably irrelevant). Now, let's say I want to take two of those points (or, better yet, add two points between those other two points), and add them onto my "mesh" to expand the original shape, and thus expand on the world (which is anything inside this polygon).

OK, so before we go *too* much farther, let me ask the best way to accomplish this -- i.e. insert two new "branch-off" points between two contiguous points in the original polygon. The order of the points would obviously need to be kept, with the two new points inserted between them. How would I go about doing that, ideally?

In case it is of any relevance, I'm using JavaScript. Also, feel free to mention any random thoughts -- problems with the idea in general, tips, related subjects to look into, and so on. Much appreciated, as always.

_________________
What most people don't understand about "enlightenment" is that it is not an end-goal; but where you find yourself just before taking a new "first step."

Top

 Post subject: Re: A procedurally generated 2D "mesh" worldPosted: Tue Jul 12, 2011 10:08 am
 Corpse Bride

Joined: Tue Jul 01, 2008 11:44 pm
Posts: 2221
Location: England
A diagram would help me understand what you want. Before and After.

_________________
I ain't pushing no moon buttons.

Top

 Post subject: Re: A procedurally generated 2D "mesh" worldPosted: Tue Jul 12, 2011 10:21 am
 Bibliotherapist

Joined: Wed Nov 03, 2004 1:28 pm
Posts: 6874
Location: Wilts, Englandshire
theraje wrote:
Hey folks, I'm sticking my big toe back into the piranha-infested waters of game programming.

Your idea sounds a little like boolean modelling tools used to build meshes in rendering packages. I've no idea how they work at the code level, but they're an established principle so there must be info around on them.

_________________
20 GOTO 10

Top

 Post subject: Re: A procedurally generated 2D "mesh" worldPosted: Wed Jul 13, 2011 1:49 am
 Harmlessness does no harm

Joined: Tue Sep 14, 2004 8:37 pm
Posts: 3913
Location: Ferriday, LA, US
@Jasmine: That could be a problem. My Web admin is on vacation at the moment, and I have to send him stuff I need uploaded.

@Codehead: Yeah, something like that, but significantly different. Main thing I want to do is add on to the "mesh", so it starts off as a square or octagon or what have you, and branches out until there's a maze/labyrinth/world going on.

_________________
What most people don't understand about "enlightenment" is that it is not an end-goal; but where you find yourself just before taking a new "first step."

Top

 Post subject: Re: A procedurally generated 2D "mesh" worldPosted: Wed Jul 13, 2011 11:06 am
 Corpse Bride

Joined: Tue Jul 01, 2008 11:44 pm
Posts: 2221
Location: England
theraje wrote:
@Jasmine: That could be a problem. My Web admin is on vacation at the moment, and I have to send him stuff I need uploaded.

Make a little jpeg, upload it here:

http://imm.io/

^^ very lightweight and simple image host,

_________________
I ain't pushing no moon buttons.

Top

 Post subject: Re: A procedurally generated 2D "mesh" worldPosted: Wed Jul 13, 2011 7:43 pm
 Bibliotherapist

Joined: Wed Nov 03, 2004 1:28 pm
Posts: 6874
Location: Wilts, Englandshire
Something like this?

An old project of mine. Used a rectangle as a start point and chopped chunks out ofthe walls to form the contours of the room.
If the extra bits were sticking out rather than in, you could extrude convoluted corridors. A bit like the Koch algorithm but with a bit of randomness thrown in.

_________________
20 GOTO 10

Top

 Post subject: Re: A procedurally generated 2D "mesh" worldPosted: Wed Jul 13, 2011 9:25 pm
 Harmlessness does no harm

Joined: Tue Sep 14, 2004 8:37 pm
Posts: 3913
Location: Ferriday, LA, US
@Codehead: Yeah, that's pretty much right on in regard to what I want to do.

_________________
What most people don't understand about "enlightenment" is that it is not an end-goal; but where you find yourself just before taking a new "first step."

Top

 Post subject: Re: A procedurally generated 2D "mesh" worldPosted: Wed Jul 13, 2011 10:03 pm
 Corpse Bride

Joined: Tue Jul 01, 2008 11:44 pm
Posts: 2221
Location: England
In Java, you could use the LinkedList class, in which each list entry is a coordinate of the polygon, which are to be listed in sequence.

The LinkedList class offers an Add method, which you can use to insert a coordinate.

JS doesn't have this class, but you can write your own, and here is a guide to doing just that:
http://blog.jcoglan.com/2007/07/23/writ ... avascript/

_________________
I ain't pushing no moon buttons.

Top

 Post subject: Re: A procedurally generated 2D "mesh" worldPosted: Thu Jul 14, 2011 3:49 am
 Harmlessness does no harm

Joined: Tue Sep 14, 2004 8:37 pm
Posts: 3913
Location: Ferriday, LA, US
Jasmine wrote:
In Java, you could use the LinkedList class, in which each list entry is a coordinate of the polygon, which are to be listed in sequence.

The LinkedList class offers an Add method, which you can use to insert a coordinate.

JS doesn't have this class, but you can write your own, and here is a guide to doing just that:
http://blog.jcoglan.com/2007/07/23/writ ... avascript/

JS doesn't have a LinkedList class, but arrays do have the splice() method, which will allow a script to insert array elements in the middle of an array.

Still, that's the easy part. What I want to find out is the best way to position the new points along the line between the two "original" points. I take it that I can just get the angle between the two points and follow that angle, inserting new points along the way? Would that be the most effective and practical way to do it, or is there a more desirable method?

_________________
What most people don't understand about "enlightenment" is that it is not an end-goal; but where you find yourself just before taking a new "first step."

Top

 Post subject: Re: A procedurally generated 2D "mesh" worldPosted: Thu Jul 14, 2011 10:27 am
 Corpse Bride

Joined: Tue Jul 01, 2008 11:44 pm
Posts: 2221
Location: England
theraje wrote:
JS doesn't have a LinkedList class, but arrays do have the splice() method, which will allow a script to insert array elements in the middle of an array.

A more low-level way of doing it is to shuffle the array, to create a gap for the new point.

Code:
Dim Polygon(1) As Point2D
Dim PolygonLength as Integer

Function InsertPoint(Position, X,Y)
PolygonLength=PolygonLength+1
ReDim Polygon(PolygonLength)
For i = PolygonLength To Position+1 Step -1
Polygon(i) = Polygon(i-1)
Next
Polygon(Position).X = X
Polygon(Position).Y = Y
End Function

Function RemovePoint(Position)
For i = Position To PolygonLength - 1
Polygon(i) = Polygon(i+1)
Next
PolygonLength=PolygonLength-1
ReDim Polygon(PolygonLength)
End Function

For calculating the coordinates of a new point, you could just take the average.

ie, if a new point (X_new, Y_new) is to be inserted between points (X1, Y1) and (X2, Y2), then

X_new = (X1 + X2)/2
Y_new = (Y1 + Y2)/2

_________________
I ain't pushing no moon buttons.

Top

 Post subject: Re: A procedurally generated 2D "mesh" worldPosted: Thu Jul 14, 2011 3:14 pm
 Harmlessness does no harm

Joined: Tue Sep 14, 2004 8:37 pm
Posts: 3913
Location: Ferriday, LA, US
Jasmine wrote:
theraje wrote:
JS doesn't have a LinkedList class, but arrays do have the splice() method, which will allow a script to insert array elements in the middle of an array.

A more low-level way of doing it is to shuffle the array, to create a gap for the new point.

Code:
Dim Polygon(1) As Point2D
Dim PolygonLength as Integer

Function InsertPoint(Position, X,Y)
PolygonLength=PolygonLength+1
ReDim Polygon(PolygonLength)
For i = PolygonLength To Position+1 Step -1
Polygon(i) = Polygon(i-1)
Next
Polygon(Position).X = X
Polygon(Position).Y = Y
End Function

Function RemovePoint(Position)
For i = Position To PolygonLength - 1
Polygon(i) = Polygon(i+1)
Next
PolygonLength=PolygonLength-1
ReDim Polygon(PolygonLength)
End Function

I'm not sure I understand the benefit of doing it that way. (If it makes any difference, JS arrays are inherently associative.)

Jasmine wrote:
For calculating the coordinates of a new point, you could just take the average.

ie, if a new point (X_new, Y_new) is to be inserted between points (X1, Y1) and (X2, Y2), then

X_new = (X1 + X2)/2
Y_new = (Y1 + Y2)/2

What if I wanted to insert two points (like a portal, which was what I was originally going for)? Would I divide the first sum by 3 and the second sum by 1.5, or is my lack of math knowledge beating me with a hole-drilled paddle once again?

_________________
What most people don't understand about "enlightenment" is that it is not an end-goal; but where you find yourself just before taking a new "first step."

Top

 Post subject: Re: A procedurally generated 2D "mesh" worldPosted: Thu Jul 14, 2011 5:10 pm
 Corpse Bride

Joined: Tue Jul 01, 2008 11:44 pm
Posts: 2221
Location: England
Linear Interpolation

Choose 'a' between 0 and 1, then let...
X_new = X0 * (1-a) + X1 * (a)
Y_new = Y0 * (1-a) + Y1 * (a)

When a is close to 0, the new point is close to (X0, Y0)
When a is close to 1, the new point is close to (X1, Y1).

To insert one point, you could use a=1/2

To insert two points you could use a=1/3 for the first point and 2/3 for the second point.

To insert three points, a=1/4 , 2/4 , 3/4 , or whatever

_________________
I ain't pushing no moon buttons.

Top

 Post subject: Re: A procedurally generated 2D "mesh" worldPosted: Thu Jul 14, 2011 8:14 pm
 Harmlessness does no harm

Joined: Tue Sep 14, 2004 8:37 pm
Posts: 3913
Location: Ferriday, LA, US
Nice.

I'll poke around a bit with it and see what I can come up with. I'll let you know how it works out, and I'll need pointers for some of the later stuff as I get to it. Thank you!

_________________
What most people don't understand about "enlightenment" is that it is not an end-goal; but where you find yourself just before taking a new "first step."

Top

 Post subject: Re: A procedurally generated 2D "mesh" worldPosted: Fri Jul 15, 2011 4:22 am
 Harmlessness does no harm

Joined: Tue Sep 14, 2004 8:37 pm
Posts: 3913
Location: Ferriday, LA, US
OK, I've gotten a chance to play with the idea some. So far, I have a demo that allows new points to be inserted between two existing points:

http://imm.io/7tUV

Now, the next step in this little excursion is extrusion. Insert two new points between two existing points as before, but with the results offset from the original points, with the angle between these two new points the same as the original angle. Take this image as an example:

http://imm.io/7tV4

The relevant information to solving this is how to figure out the X/Y coordinates of the new points. I will try and dig up some info in the meantime, but your thoughts/methods are welcome.

(EDIT: Changed image tags to links, as the imm.io site doesn't seem to allow hot-linking)

_________________
What most people don't understand about "enlightenment" is that it is not an end-goal; but where you find yourself just before taking a new "first step."

Top

 Post subject: Re: A procedurally generated 2D "mesh" worldPosted: Fri Jul 15, 2011 10:40 am
 Corpse Bride

Joined: Tue Jul 01, 2008 11:44 pm
Posts: 2221
Location: England
Firstly, imm.io does allow hotlinking -- right click the image, and copy the image location.

like this:

Extrusion i's fairly straight forward to do.

First is to get the direction vector "u" between vertices 0 and 1.
Code:
ux = X1 - X0
uy = Y1 - Y0

Then, we must normalise the vector by dividing by it's length.
Code:
ul = (ux^2 + uy^2)^0.5
ux = ux / ul
uy = uy / ul

Then we must create an extrusion vector "v" by rotating "u" anticlockwise 90 degrees, and multiplying it by the extrusion distance "b"
Code:
vx = -uy * b
vy = ux * b

The four points are then
Code:
Original Point 0: (x0,y0)
New Point 1: (x0,y0) + extrusion vector (vx, vy)  = (x0+vx,, y0+vy)
New Point 2: (x1,y1) + extrusion vector (vx, vy)  = (x1+vx, y1+vy)
Original Point 1: ( x1,y1)

_________________
I ain't pushing no moon buttons.

Top

 Post subject: Re: A procedurally generated 2D "mesh" worldPosted: Wed Jul 27, 2011 12:04 pm
 Corpse Bride

Joined: Tue Jul 01, 2008 11:44 pm
Posts: 2221
Location: England
Did you get any further with this theraje?

_________________
I ain't pushing no moon buttons.

Top

 Post subject: Re: A procedurally generated 2D "mesh" worldPosted: Wed Jul 27, 2011 1:56 pm
 Harmlessness does no harm

Joined: Tue Sep 14, 2004 8:37 pm
Posts: 3913
Location: Ferriday, LA, US
I got everything discussed here working. And then I got involved in Lurker, so that's been my "primary" project lately (although I'm currently stuck in a rut with it trying to rework some ideas).

I also bought a new power supply for my PlayStation 2 (my aunt borrowed my old adapter because my cousin borrowed her adapter since my cousin left his at a friend's house and the friend moved). So yeah, not much attention has been centered upon this little excursion.

_________________
What most people don't understand about "enlightenment" is that it is not an end-goal; but where you find yourself just before taking a new "first step."

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 17 posts ]

 All times are UTC

#### Who is online

Users browsing this forum: No registered users and 1 guest

 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forum

Search for:
 Jump to:  Select a forum ------------------ Forums    Forum Rules and Posting Guidelines Wiki Discussion    Help    Content Issues Game Programming Discussion    C and C++ Game Programming    Java Game Programming    Language Agnostic Programming    .NET Game Programming    VB Game Programming    Mobile Game Programming    Web-Based Game Programming    Other Languages    OpenGL Development    Direct X Development Game Development Discussion    Game Design    Game Media Off-Topic Discussion    Announcements    Off-Topic    Community Projects    News