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."

A diagram would help me understand what you want. Before and After.

_________________
I ain't pushing no moon buttons.

Glad to hear it.

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.

_________________
10 PRINT "Bad Monkey ";
20 GOTO 10

@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."

Make a little jpeg, upload it here:

http://imm.io/

^^ very lightweight and simple image host,

_________________
I ain't pushing no moon buttons.

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.

_________________
10 PRINT "Bad Monkey ";
20 GOTO 10

@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."

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.

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."

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



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.

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



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."

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.

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."

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."

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.


Then, we must normalise the vector by dividing by it's length.



Then we must create an extrusion vector "v" by rotating "u" anticlockwise 90 degrees, and multiplying it by the extrusion distance "b"


The four points are then

_________________
I ain't pushing no moon buttons.

Did you get any further with this theraje?

_________________
I ain't pushing no moon buttons.

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."