Sorry your browser is not supported!

set display mode desktop width(), desktop height(), 32
sync on : sync rate 60 : sync

tolerance# = 0.0001
for vec = 1 to 10 ` just in case we need them
  null = make vector3(vec)
next vec

type vertex
  x as float
  y as float
  z as float
endtype

A as vertex
B as vertex
C as vertex
P as vertex

// create three vertices for the triangle
`A.x = 10.0 : A.y = 20.0 : A.z = 10.0
`B.x = 10.0 : B.y = 20.0 : B.z = 20.0
`C.x = 20.0 : C.y = 10.0 : C.z = 10.0

// RUSSIA's example
A.x =-9.98715591431
A.y =0
A.z =-3.32904601097
B.x =-9.98715782166
B.y =28.571428299
B.z =-9.98715019226
C.x =-9.98715782166
C.y =0
C.z =-9.98715019226
P.x =-9.98715209961
P.y =17.4658203125
P.z =-9.09385681152

// set the candidate point to the centre of the triangle - this is inside the triangle
//P.x = (A.x+B.x+C.x)/3.0 : P.y = (A.y+B.y+C.y)/3.0 : P.z = (A.z+B.z+C.z)/3.0
// use DBPro 3DMaths commands to calculate normal vector
setVector3(1, A)
setVector3(2, B)
setVector3(3, C)
setVector3(7, P)

subtract vector3 5, 2, 1 ` this is B-A
subtract vector3 6, 3, 1 ` this is C-A
subtract vector3 8, 7, 1 ` this is the vector P-A
cross product vector3 4,5,6
normalize vector3 4,4 ` this is the normal vector N

// calculate w value for testing whether P is inside the triangle
w# = dot product vector3 (8, 4) ` this is the dotproduct (P-A).N

// test whether P is in the same plane as the triangle (within a certain error tolerance)
if abs(w#)<= tolerance#
  print "w = ", w#, " P is in the same plane as the triangle, therefore test if also inside triangle"
  // construct 2x2 matrix, etc, for solving the equations using standard least squares procedure
  A11# = dot product vector3(5, 5)
  A12# = dot product vector3(5, 6)
  A22# = dot product vector3(6, 6)
  B1# = dot product vector3(5, 8)
  B2# = dot product vector3(6, 8)
  // scale cefficients to reduce precision problems when testing determinant
  factor# = 1.0/max(A11#, A22#)
  A11# = A11#*factor#
  A12# = A12#*factor#
  A22# = A22#*factor#
  B1# = B1#*factor#
  B2# = B2#*factor#
  // compute determinant of 2x2 matrix
  det# = A11#*A22# - A12#*A12#
  if abs(det#) > tolerance#
    ` solve for u and v
    u# = (A22#*B1# - A12#*B2#)/det#
    v# = (-A12#*B1# + A11#*B2#)/det#
  else
    ink rgb(255, 0, 0)
    print " triangle may be degenerate - check vertices:"
    print " A = ", A.x, " ", A.y, " ", A.z
    print " B = ", B.x, " ", B.y, " ", B.z
    print " C = ", C.x, " ", C.y, " ", C.z
    sync
    wait key
    end
  endif
  if (u# >= -tolerance#) and (v# >= -tolerance#) and (u#+v# <= 1.0+tolerance#)
    ink rgb(0, 255, 0), 0
    print " u, v = ", " ", u#, " ", v#
    print " Yes!!! Point is inside triangle"
  else
    ink rgb(255, 0, 0), 0
    print " u, v = ", " ", u#, " ", v#
    print " Sorry! Point is not inside triangle"
  endif
else
  ink rgb(255, 0, 0), 0
  print " w = ", w#, " P is not even in the same plane as triangle so cannot be inside it"
endif
sync
wait key

end

function setVector3(id, V as vertex)
  set vector3 id, V.x, V.y, V.z
endfunction

function _IN_POLY()
    x as float : x1 as float : x2 as float : x3 as float
    y as float : y1 as float : y2 as float : y3 as float
    
    ` flag for checking the triangles
    flag = 0
    
    ` new point x, y
    _MAP_TEMP_X = _MAP_TEMP_X + ( _LINE_LEN * acos( _MAP_TEMP_ANG ) )
    _MAP_TEMP_Y = _MAP_TEMP_Y + ( _LINE_LEN * asin( _MAP_TEMP_ANG ) )
    
    x = _MAP_TEMP_X
    y = _MAP_TEMP_Y
    
    ` start of face for this map
    elem = _MAP(_mapID).f2p
    count = array count( _FACES() ) - elem
    
    while count > 0 and flag = 0
        ` heres were I implement the code
        x1 = _VERTS(_FACES(elem).p1).x
        y1 = _VERTS(_FACES(elem).p1).y
        x2 = _VERTS(_FACES(elem).p2).x
        y2 = _VERTS(_FACES(elem).p2).y
        x3 = _VERTS(_FACES(elem).p3).x
        y3 = _VERTS(_FACES(elem).p3).y
        
        if _IN_TRIANGLE(x,y,x1,y1,x2,y2,x3,y3)
            flag=1
        endif
        
        dec count
    endwhile
endfunction flag

` ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

function _IN_TRIANGLE(x as float, y as float, x1 as float, y1 as float, x2 as float, y2 as float, x3 as float, y3 as float)
   local AB as float
   local BC as float
   local CA as float

   AB = ((y-y1)*(x2-x1)) - ((x-x1)*(y2-y1))
   BC = ((y-y2)*(x3-x2)) - ((x-x2)*(y3-y2))
   if AB * BC <= 0 then exitfunction 0

   CA = (y-y3)*(x1-x3) - (x-x3)*(y1-y3)
   if BC * CA <= 0 then exitfunction 0
endfunction

function _PICK_ANGLE(edge)
    edge_angle as float
    x as float
    y as float
    
    x = _VERTS( _OUTER(edge).s ).x
    y = _VERTS( _OUTER(edge).s ).y
    
    _MAP_TEMP_X = _VERTS( _OUTER(edge).e ).x - x
    _MAP_TEMP_Y = _VERTS( _OUTER(edge).e ).y - y
    
    ` get current lines angle
    edge_angle = atanfull(_MAP_TEMP_X, _MAP_TEMP_Y)
    
    ` adjust it
    _MAP_TEMP_ANG = wrapvalue( edge_angle - _ANGLE_MIN + rnd( _ANGLE_RNG ) )
endfunction

` store new points position
    _MAP_TEMP_X = x + ( _LINE_LEN * cos( _MAP_TEMP_ANG ) )
    _MAP_TEMP_Y = y + ( _LINE_LEN * sin( _MAP_TEMP_ANG ) )

function _PICK_EDGE(mapID)
    start = _MAP(mapID).e2p
    count = array count( _OUTER() ) - start
    edge = rnd(count) + start
endfunction edge

` ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

function _PICK_ANGLE(edge)
    edge_angle as float
    x as float
    y as float
    
    x = _VERTS( _OUTER(edge).s ).x
    y = _VERTS( _OUTER(edge).s ).y
    
    ` get line lengths
    _MAP_TEMP_X = _VERTS( _OUTER(edge).e ).x - x
    _MAP_TEMP_Y = _VERTS( _OUTER(edge).e ).y - y
    
    ` get current lines angle
    edge_angle = atanfull(_MAP_TEMP_X, _MAP_TEMP_Y)
    
    ` adjust it
    `_MAP_TEMP_ANG = wrapvalue( edge_angle - _ANGLE_MIN + rnd( _ANGLE_RNG ) )
    _MAP_TEMP_ANG = wrapvalue( edge_angle - (45.0 + 270.0) )
    
    ` store new points position
    _MAP_TEMP_X = x + ( _LINE_LEN * cos( _MAP_TEMP_ANG ) )
    _MAP_TEMP_Y = y + ( _LINE_LEN * sin( _MAP_TEMP_ANG ) )

endfunction

void MAP_DATA::generate() {
	int		face = 1;		// we're creating the first one anyway
	float	x1,y1, x2,y2, x3,y3, x,y;
	int		edge;			// random picked edge
	int		v1,v2,v3;		// vertex indices
	float	angle;			// angle of and edge

	char	str[100];

	// create first triangle
	verts.push_back( _VERT(0,0) );
	verts.push_back( _VERT(edge_length,0) );
	verts.push_back( _VERT(0,edge_length) );

	// add its edges to the outer list
	outer.push_back( _EDGE(0,1) );
	outer.push_back( _EDGE(1,2) );
	outer.push_back( _EDGE(2,0) );

	// make the first face
	faces.push_back( _FACE(0,1,2) );

	// init the pseudo random number generator
	srand( rnd_seed );

	while ( face <= max_faces ) {
		sprintf(WLT_TEXT,"Edges:%d",outer.size()); WLT_WRITE();

		// pick a random edge first
		edge = rand() % outer.size();	// between 0 and size-1

		// grab the current vertex indices (v2 will be the new one)
		v1 = outer[ edge ].start;
		v3 = outer[ edge ].end;

		// get the current angle of the line
		angle = atan2( verts[v3].x - verts[v1].x, verts[v3].y - verts[v1].y );

		// now to alter the angle (subtract 45 degrees)
		angle -= ( 3.14159265 / 4.0f );		// 45 deg = pi/4
		if ( angle < -3.14159265 )			// wrap it
			angle += 2 * 3.14159265;

		// set new coords
		x = verts[ outer[ edge ].start ].x + ( cos( angle ) * edge_length );
		y = verts[ outer[ edge ].start ].y + ( sin( angle ) * edge_length );

		sprintf(WLT_TEXT,"Edge:%d, Angle: %f, Coords:%f, %f",edge,angle,x,y); WLT_WRITE();

		// check if it inside the main polygon outline
		{
			// using local variables for a little speed boost
			int		face_count = faces.size();
			bool	flag = 0;

			float	ab, bc, ca;

			vector<_EDGE>::iterator it;

			while ( face_count > 0 && flag == 0 ) {
				face_count--;

				// get triangle coords of face
				x1 = verts[faces[face_count].v1].x;
				y1 = verts[faces[face_count].v1].y;

				x2 = verts[faces[face_count].v2].x;
				y2 = verts[faces[face_count].v2].y;

				x3 = verts[faces[face_count].v3].x;
				y3 = verts[faces[face_count].v3].y;

				// is new point in the triangle
				ab = ((y-y1)*(x2-x1)) - ((x-x1)*(y2-y1));
				bc = ((y-y2)*(x3-x2)) - ((x-x2)*(y3-y2));

				if ( ab * bc > 0 ) {
					ca = (y-y3)*(x1-x3) - (x-x3)*(y1-y3);
					if ( bc * ca > 0 )
						flag = 1;	// tell the polygon search to stop
				}
			} // EOF while ( face_count > 0)

			if ( flag == 0 ) {
				// add the new vertex
				verts.push_back( _VERT(x,y) );

				// remove edge from main polygon
				inner.push_back( _EDGE(outer[edge].start,outer[edge].end) );
				it = outer.begin() + edge;
				outer.erase( it );

				// now set v2 as new vertex
				v2 = verts.size() - 1;

				// add the two new edges
				outer.push_back( _EDGE(v1,v2) );
				outer.push_back( _EDGE(v2,v3) );

				// add the triangle to the faces list
				faces.push_back( _FACE(v1,v2,v3) );

				// increment the main face counter
				face++;

				// Write TRACE
				sprintf(WLT_TEXT,"Faces=%d, Verts=%d",faces.size(),verts.size()); WLT_WRITE();
			}
		} // EOF internal braces (optimised for local vars)

	} // EOF while ( face <= max_faces )
}

void MAP_DATA::generate() {
	int		face = 1;		// we're creating the first one anyway
	float	x1,y1, x2,y2, x3,y3, x,y;
	int		edge;			// random picked edge
	int		v1,v2,v3;		// vertex indices
	float	angle;			// angle of and edge
	float	edge_alt;		// alteration in lines length

	// create first triangle
	verts.push_back( _VERT(0,0) );
	verts.push_back( _VERT(edge_length,0) );
	verts.push_back( _VERT(0,edge_length) );

	// add its edges to the outer list
	outer.push_back( _EDGE(0,1) );
	outer.push_back( _EDGE(1,2) );
	outer.push_back( _EDGE(2,0) );

	// make the first face
	faces.push_back( _FACE(0,1,2) );

	// init the pseudo random number generator
	srand( rnd_seed );

	while ( face < max_faces ) {
		//sprintf(WLT_TEXT,"Edges:%d",outer.size()); WLT_WRITE();

		// pick a random edge first
		edge = rand() % outer.size();	// between 0 and size-1

		// grab the current vertex indices (v2 will be the new one)
		v1 = outer[ edge ].start;
		v3 = outer[ edge ].end;

		// get the current angle of the line
		angle = atan2( verts[v3].y - verts[v1].y, verts[v3].x - verts[v1].x );

		// now to alter the angle (subtract 45 degrees)
		angle -= ( 3.14159265f / 4.0f );		// 45 deg = pi/4
		if ( angle < -3.14159265f )			// wrap it
			angle += ( 2.0f * 3.14159265f );

		edge_alt = edge_length - ( ( (float)( rand() % 5 ) + 5.0f ) / 10.0f );

		// set new coords
		x = verts[ outer[ edge ].start ].x + ( cos( angle ) * edge_alt );
		y = verts[ outer[ edge ].start ].y + ( sin( angle ) * edge_alt );

		//sprintf(WLT_TEXT,"Edge:%d, Angle: %f, Coords:%f, %f",edge,angle,x,y); WLT_WRITE();

		// check if it inside the main polygon outline
		{
			// using local variables for a little speed boost
			int		face_count = faces.size();
			bool	flag = 0;

			float	ab, bc, ca;

			vector<_EDGE>::iterator it;

			while ( face_count > 0 && flag == 0 ) {
				face_count--;

				// get triangle coords of face
				x1 = verts[faces[face_count].v1].x;
				y1 = verts[faces[face_count].v1].y;

				x2 = verts[faces[face_count].v2].x;
				y2 = verts[faces[face_count].v2].y;

				x3 = verts[faces[face_count].v3].x;
				y3 = verts[faces[face_count].v3].y;

				// is new point in the triangle
				ab = ((y-y1)*(x2-x1)) - ((x-x1)*(y2-y1));
				bc = ((y-y2)*(x3-x2)) - ((x-x2)*(y3-y2));

				if ( ab * bc > 0.0f ) {
					ca = (y-y3)*(x1-x3) - (x-x3)*(y1-y3);
					if ( bc * ca > 0.0f )
						flag = 1;	// tell the polygon search to stop
				}
			} // EOF while ( face_count > 0)

			if ( flag == 0 ) {
				// add the new vertex
				verts.push_back( _VERT(x,y) );

				// remove edge from main polygon
				inner.push_back( _EDGE(outer[edge].start,outer[edge].end) );
				it = outer.begin() + edge;
				outer.erase( it );

				// now set v2 as new vertex
				v2 = verts.size() - 1;

				// add the two new edges
				outer.push_back( _EDGE(v1,v2) );
				outer.push_back( _EDGE(v2,v3) );

				// add the triangle to the faces list
				faces.push_back( _FACE(v1,v2,v3) );

				// increment the main face counter
				face++;

				// Write TRACE
				//sprintf(WLT_TEXT,"Faces=%d, Verts=%d",faces.size(),verts.size()); WLT_WRITE();
			}
		} // EOF internal braces (optimised for local vars)

	} // EOF while ( face <= max_faces )

	// Now to test it by creating the faces as TRIANGLE OBJECTs for GDK
	sprintf(WLT_TEXT,"Totals - Verts:%d, OutEdge:%d, InEdge:%d, Faces:%d",
		verts.size(), outer.size(), inner.size(), faces.size());
	WLT_WRITE();

	for ( face = 0; face < faces.size(); face++ ) {
		x1 = verts[ faces[ face ].v1 ].x;
		y1 = verts[ faces[ face ].v1 ].y;

		x2 = verts[ faces[ face ].v2 ].x;
		y2 = verts[ faces[ face ].v2 ].y;

		x3 = verts[ faces[ face ].v3 ].x;
		y3 = verts[ faces[ face ].v3 ].y;

		v1 = free_obj();
		ObjID.push_back( v1 );

		dbMakeObjectTriangle( v1, x1,0,y1, x2,0,y2, x3,0,y3 );
		dbSetObject( v1,0,0,0 );
	}
}

Point* intersection(Point p1, Point p2, Point p3, Point p4) {
// Store the values for fast access and easy
// equations-to-code conversion
float x1 = p1.x, x2 = p2.x, x3 = p3.x, x4 = p4.x;
float y1 = p1.y, y2 = p2.y, y3 = p3.y, y4 = p4.y;

float d = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4);
// If d is zero, there is no intersection
if (d == 0) return NULL;

// Get the x and y
float pre = (x1*y2 - y1*x2), post = (x3*y4 - y3*x4);
float x = ( pre * (x3 - x4) - (x1 - x2) * post ) / d;
float y = ( pre * (y3 - y4) - (y1 - y2) * post ) / d;

// Check if the x and y coordinates are within both lines
if ( x < min(x1, x2) || x > max(x1, x2) ||
x < min(x3, x4) || x > max(x3, x4) ) return NULL;
if ( y < min(y1, y2) || y > max(y1, y2) ||
y < min(y3, y4) || y > max(y3, y4) ) return NULL;

// Return the point of intersection
Point* ret = new Point();
ret->x = x;
ret->y = y;
return ret;
}

function _PICK_EDGE_ANGLE()
    ang as float
    x as float
    y as float

    start = _MAP(_mapID).e2p
    count = array count( _OUTER() ) - start
    edge = rnd(count) + start
    
    x = _VERTS( _OUTER(edge).s ).x
    y = _VERTS( _OUTER(edge).s ).y
    
    ` get line lengths
    _MAP_TEMP_X = _VERTS( _OUTER(edge).e ).x - x
    _MAP_TEMP_Y = _VERTS( _OUTER(edge).e ).y - y
    
    ` get current lines angle
    ang = atanfull(_MAP_TEMP_Y, _MAP_TEMP_X)
    
    ` adjust it
    `_MAP_TEMP_ANG = wrapvalue( ang - _ANGLE_MIN + rnd( _ANGLE_RNG ) )
    _MAP_TEMP_ANG = wrapvalue( ang - 45 )
    
    ` store new points position
    _MAP_TEMP_X = x + ( _LINE_LEN * cos( _MAP_TEMP_ANG ) )
    _MAP_TEMP_Y = y + ( _LINE_LEN * sin( _MAP_TEMP_ANG ) )

endfunction edge

void MAP_DATA::generate() {
	int		face = 1;		// we're creating the first one anyway
	//float	x1,y1, x2,y2, x3,y3; These are now used in local braces for a speed boost
	float	x,y;
	int		edge;			// random picked edge
	int		v1,v2,v3;		// vertex indices
	float	angle;			// angle of and edge
	float	edge_alt;		// alteration in lines length

	// create first triangle
	verts.push_back( _VERT(0,0) );
	verts.push_back( _VERT(edge_length,0) );
	verts.push_back( _VERT(0,edge_length) );

	// add its edges to the outer list
	outer.push_back( _EDGE(0,1) );
	outer.push_back( _EDGE(1,2) );
	outer.push_back( _EDGE(2,0) );

	// make the first face
	faces.push_back( _FACE(0,1,2) );

	// init the pseudo random number generator
	srand( rnd_seed );

	while ( face < max_faces ) {
		//sprintf(WLT_TEXT,"Edges:%d",outer.size()); WLT_WRITE();

		// pick a random edge first
		edge = rand() % outer.size();	// between 0 and size-1

		// grab the current vertex indices (v2 will be the new one)
		v1 = outer[ edge ].start;
		v3 = outer[ edge ].end;

		// get the current angle of the line
		angle = atan2( verts[v3].y - verts[v1].y, verts[v3].x - verts[v1].x );

		// now to alter the angle (subtract 45 degrees)
		angle -= ( 3.14159265f / 4.0f );		// 45 deg = pi/4
		if ( angle < -3.14159265f )			// wrap it
			angle += ( 2.0f * 3.14159265f );

		// alter the edges length by upto 50%
		edge_alt = edge_length * ( ( (float)( rand() % 5 ) + 5.0f ) / 10.0f );

		// set new coords
		x = verts[ outer[ edge ].start ].x + ( cos( angle ) * edge_alt );
		y = verts[ outer[ edge ].start ].y + ( sin( angle ) * edge_alt );

		//sprintf(WLT_TEXT,"Edge:%d, Angle: %f, Coords:%f, %f",edge,angle,x,y); WLT_WRITE();

		// now to check if the two new lines intersect with
		// the main polygon outline
		{
			// using these braces to optimise some local variables
			float	x1,y1, x2,y2, x3,y3, x4,y4;
			int		curr_edge;
			bool	flag = 0;
			float	d;
			float	angle;

			curr_edge = outer.size();

			sprintf(WLT_TEXT,"Outer edge count = %d",curr_edge); WLT_WRITE();

			// store new edges coords for BOTH lines

			// first line is x1,y1, x,y
			x1 = verts[ outer[ v1 ].start ].x;
			y1 = verts[ outer[ v1 ].start ].y;

			// second line is x,y, x2,y2
			x2 = verts[ outer[ v3 ].end ].x;
			y2 = verts[ outer[ v3 ].end ].y;

			// Here's where I need to slightly alter the x1,y1 & x2,y2
			// This is because the line will intersect with neighbouring
			// edges because they use the same vertices. I'll experiment
			// by moving a percentage of the beggining points towards
			// the end points.

			// The triangle is now made up of x1,y1, x,y, x2,y2
			// x,y are the new coords of the vertex that might get added
			// if all checks later work out correct.

			/*angle = atan2( y - y1, x - x1 );
			x1 += cos( angle ) * 2.0f;
			y1 += sin( angle ) * 2.0f;

			angle = atan2( y - y2, x - x2 );
			x2 += cos( angle ) * 2.0f;
			y2 += sin( angle ) * 2.0f;*/

			// I've taken the above out because it didn't work.
			// However, I have realised that a simpler check should work.
			// If any of the vertices are the same then don't do the line
			// intersect check. Jobs a good'un...

			while ( curr_edge > 0 && flag == 0 ) {
				// some more local variables for speed boost
				float	pre, post, xc, yc;
				int		vs, ve;		// edge vertices

				curr_edge--;

				/*sprintf(WLT_TEXT,"curr_edge=%d",curr_edge);
				WLT_WRITE();*/

				if ( curr_edge != edge ) { // skip if same edge
					// edges line in x3,y3, x4,y4
					vs = outer[ curr_edge ].start;

					x3 = verts[ vs ].x;
					y3 = verts[ vs ].y;

					ve = outer[ curr_edge ].end;

					x4 = verts[ ve ].x;
					y4 = verts[ ve ].y;

					// Now check 1st new line
					if ( ve == v1 )
						d = 0;
					else
						d = (x1 - x) * (y3 - y4) - (y1 - y) * (x3 - x4);

					if ( d != 0 ) {
						// got an intersection
						pre = (x1*y - y1*x);
						post = (x3*y4 - y3*x4);

						xc = ( pre * (x3 - x4) - (x1 - x) * post ) / d;
						yc = ( pre * (y3 - y4) - (y1 - y) * post ) / d;

						// check if coords are in both lines
						if ( xc >= min(x1, x) && xc <= max(x1, x) &&
							xc >= min(x3, x4) && xc <= max(x3, x4) ) 
						{
							if ( yc >= min(y1, y) && yc <= max(y1, y) &&
								yc >= min(y3, y4) && yc <= max(y3, y4) ) 
							{
								flag = 1; // tell the rest to stop
							}
						}
					} // EOF if ( d != 0 )

					// Now check the second line x,y, x2,y2
					if ( flag == 0 ) { // skip if flag already set
						if ( vs == v3 )
							d = 0;
						else
							d = (x - x2) * (y3 - y4) - (y - y2) * (x3 - x4);

						if ( d != 0 ) {
							// got an intersection
							pre = (x*y2 - y*x2);
							post = (x3*y4 - y3*x4);

							xc = ( pre * (x3 - x4) - (x - x2) * post ) / d;
							yc = ( pre * (y3 - y4) - (y - y2) * post ) / d;

							// check if coords are in both lines
							if ( xc >= min(x, x2) && xc <= max(x, x2) &&
								xc >= min(x3, x4) && xc <= max(x3, x4) ) 
							{
								if ( yc >= min(y, y2) && yc <= max(y, y2) &&
									yc >= min(y3, y4) && yc <= max(y3, y4) ) 
								{
									flag = 1; // tell the rest to stop
								}
							}
						} // EOF if ( d != 0 )
					} // EOF if ( flag == 0 )

				} // EOF if ( curr_edge != edge )

			} // EOF while ( curr_edge > 0 )

			// If the flag has not been set then add the new face to the list
			if ( flag == 0 ) {
				vector<_EDGE>::iterator it;

				// add the new vertex
				verts.push_back( _VERT(x,y) );

				// remove edge from main polygon
				inner.push_back( _EDGE(outer[edge].start,outer[edge].end) );
				it = outer.begin() + edge;
				outer.erase( it );

				// now set v2 as new vertex
				v2 = verts.size() - 1;

				// add the two new edges
				outer.push_back( _EDGE(v1,v2) );
				outer.push_back( _EDGE(v2,v3) );

				// add the triangle to the faces list
				faces.push_back( _FACE(v1,v2,v3) );

				// increment the main face counter
				face++;
			}

		} // EOF optimised locals for line intersect check

	} // EOF while ( face <= max_faces )

	// Now to test it by creating the faces as TRIANGLE OBJECTs for GDK
	sprintf(WLT_TEXT,"Totals - Verts:%d, OutEdge:%d, InEdge:%d, Faces:%d",
		verts.size(), outer.size(), inner.size(), faces.size());
	WLT_WRITE();

	for ( face = 0; face < faces.size(); face++ ) {
		float x1,y1, x2,y2, x3,y3;

		x1 = verts[ faces[ face ].v1 ].x;
		y1 = verts[ faces[ face ].v1 ].y;

		x2 = verts[ faces[ face ].v2 ].x;
		y2 = verts[ faces[ face ].v2 ].y;

		x3 = verts[ faces[ face ].v3 ].x;
		y3 = verts[ faces[ face ].v3 ].y;

		v1 = free_obj();
		ObjID.push_back( v1 );

		dbMakeObjectTriangle( v1, x1,0,y1, x2,0,y2, x3,0,y3 );
		dbSetObject( v1,0,0,0 );
	}
}

class _VERT {
public:
	float	x,y;

	inline _VERT() { x=y=0; }
	inline _VERT(float xx, float yy) { x=xx; y=yy; }
};

class _EDGE {
public:
	int		start, end;

	inline _EDGE() { start=end=0; }
	inline _EDGE(int v1, int v2) { start=v1; end=v2; }
};

class _FACE {
public:
	int		v1, v2, v3;
	inline	_FACE() { v1=v2=v3=0; }
	inline	_FACE(int p1, int p2, int p3) { v1=p1; v2=p2; v3=p3; }
};

class MAP_DATA {
public:
	vector<_VERT>	verts;
	vector<_EDGE>	outer;
	vector<_EDGE>	inner;
	vector<_FACE>	faces;

	vector<int>		ObjID;

	int				max_faces;
	int				rnd_seed;
	float			edge_length;

	MAP_DATA();
	~MAP_DATA();

	void			generate();
};

void MAP_DATA::generate() {
	int		face = 2;		// we're creating the first two anyway
	//float	x1,y1, x2,y2, x3,y3, x4,y4;
	float	x,y;
	int		edge;			// random picked edge
	int		v1,v3;		// vertex indices
	float	angle;			// angle of and edge
	float	edge_alt;		// alteration in lines length

	make_first_poly();

	// init the pseudo random number generator
	srand( rnd_seed );

	while ( face < max_faces ) {
		// pick a random edge first
		edge = rand() % outer.size();	// between 0 and size-1

		// grab the current vertex indices (v2 will be the new one)
		v1 = outer[ edge ].start; v3 = outer[ edge ].end;

		// get the current angle of the line
		angle = atan2( verts[v3].y - verts[v1].y, verts[v3].x - verts[v1].x );

		// now to alter the angle (subtract 45 degrees) and wrap it
		angle -= edge_angle;		// 45 deg = pi/4
		if ( angle < -3.14159265f )	angle += ( 2.0f * 3.14159265f );

		// alter the edges length using the values in MAP_DATA now
		edge_alt = edge_length * ( (float)(( rand() % rnd_mod ) + rnd_add ) / rnd_div );

		// set new coords
		x = verts[ outer[ edge ].start ].x + ( cos( angle ) * edge_alt );
		y = verts[ outer[ edge ].start ].y + ( sin( angle ) * edge_alt );

		if ( face_in_poly(edge,x,y) == 0 ) {
			add_face(x,y,edge);
			face++; }

	} // EOF while ( face <= max_faces )

	// Now to test it by creating the faces as TRIANGLE OBJECTs for GDK
	sprintf(WLT_TEXT,"Totals - Verts:%d, OutEdge:%d, InEdge:%d, Faces:%d", verts.size(), outer.size(), inner.size(), faces.size()); WLT_WRITE();

	test_faces();
}

`%walking triangle test%
`======================
`©P.Parkinson
`======================
`Main Source File

`*********************************
`enviroment set up

IF CHECK DISPLAY MODE(1024,768,32) 
	SET DISPLAY MODE 1024,768,32
	h=DESKTOP HEIGHT()
	w=DESKTOP WIDTH()
	posx=w/2-512
	posy=h/2-384
ELSE
	SET DISPLAY MODE 640,480,32
	h=DESKTOP HEIGHT()
	w=DESKTOP WIDTH()
	posx=w/2-320
	posy=h/2-240
ENDIF
SET WINDOW POSITION posx,posy

SYNC ON
SYNC RATE 0
AUTOCAM OFF
HIDE MOUSE
COLOR BACKDROP 0,0
SET TEXT FONT "Arial"
SET TEXT SIZE 12
SET TEXT TRANSPARENT

POSITION CAMERA 0,300,0
POINT CAMERA 0,0,0

POSITION MOUSE SCREEN WIDTH()/2,SCREEN HEIGHT()/2
dummy=MOUSEMOVEX()
dummy=MOUSEMOVEY()
SYNC
D3D_INIT
RANDOMIZE (TIMER())

``use your own textures for testing
LOAD IMAGE "floor.jpg",1
load image "ceiling.jpg",2
LOAD IMAGE "wall.jpg",3
`*********************************	
`declarations and setup starts here

``vectors for collision detection 
GLOBAL point1 AS INTEGER=1
GLOBAL point2 AS INTEGER=2
GLOBAL point3 AS INTEGER=3
GLOBAL point4 AS INTEGER=4
GLOBAL result1 AS INTEGER=5
GLOBAL result2 AS INTEGER=6
GLOBAL result3 AS INTEGER=7
GLOBAL result4 AS INTEGER=8
GLOBAL result5 AS INTEGER=9
GLOBAL result6 AS INTEGER=10

dummy=MAKE VECTOR3(point1)
dummy=MAKE VECTOR3(point2)
dummy=MAKE VECTOR3(point3)
dummy=MAKE VECTOR3(point4)
dummy=MAKE VECTOR3(result1)
dummy=MAKE VECTOR3(result2)
dummy=MAKE VECTOR3(result3)
dummy=MAKE VECTOR3(result4)
dummy=MAKE VECTOR3(result5)
dummy=MAKE VECTOR3(result6)

TYPE triangle
	ax AS FLOAT
	az AS FLOAT
	bx AS FLOAT
	bz AS FLOAT
	cx AS FLOAT
	cz AS FLOAT
	ab_used AS INTEGER
	bc_used AS INTEGER
	ca_used AS INTEGER
ENDTYPE

TYPE intersect
	ab_x AS FLOAT
	ab_z AS FLOAT
	ab_dist AS FLOAT
	bc_x AS FLOAT
	bc_z AS FLOAT
	bc_dist AS FLOAT
	ca_x AS FLOAT
	ca_z AS FLOAT
	ca_dist AS FLOAT
ENDTYPE

GLOBAL triangle_size AS FLOAT:triangle_size=50.0
GLOBAL max_triangles AS INTEGER=250
GLOBAL current_triangle AS INTEGER=1
DIM triangle_data(max_triangles) AS triangle
DIM new_triangle_data(1) AS triangle
DIM intersect_data(1) AS intersect
GLOBAL triangle_to_use AS INTEGER

``make intersection markers
GLOBAL dummy_ab AS INTEGER=10001
GLOBAL dummy_bc AS INTEGER=10002
GLOBAL dummy_ca AS INTEGER=10003
MAKE OBJECT BOX dummy_ab,1,1,1
MAKE OBJECT BOX dummy_bc,1,1,1
MAKE OBJECT BOX dummy_ca,1,1,1
COLOR OBJECT dummy_ab,RGB(255,0,0)
COLOR OBJECT dummy_bc,RGB(0,255,0)
COLOR OBJECT dummy_ca,RGB(0,0,255)

``make initial triangle
make_new_triangle()
copy_new_to_triangle_list()
MAKE OBJECT TRIANGLE current_triangle,triangle_data(current_triangle).ax,0,triangle_data(current_triangle).az,triangle_data(current_triangle).bx,0,triangle_data(current_triangle).bz,triangle_data(current_triangle).cx,0,triangle_data(current_triangle).cz
SET OBJECT WIREFRAME current_triangle,1
SYNC

//`make a series of start points
//DO
//	make_new_triangle()
//	move_triangle()
//	D3D_LINE3D new_triangle_data(1).ax,0.0,new_triangle_data(1).az,new_triangle_data(1).bx,0.0,new_triangle_data(1).bz,RGB(255,0,0),1
//	D3D_LINE3D new_triangle_data(1).bx,0.0,new_triangle_data(1).bz,new_triangle_data(1).cx,0.0,new_triangle_data(1).cz,RGB(0,255,0),1
//	D3D_LINE3D new_triangle_data(1).cx,0.0,new_triangle_data(1).cz,new_triangle_data(1).ax,0.0,new_triangle_data(1).az,RGB(0,0,255),0
//	
//	IF check_if_valid()=0
//		INC current_triangle
//		copy_new_to_triangle_list()
//		MAKE OBJECT TRIANGLE current_triangle,triangle_data(current_triangle).ax,0,triangle_data(current_triangle).az,triangle_data(current_triangle).bx,0,triangle_data(current_triangle).bz,triangle_data(current_triangle).cx,0,triangle_data(current_triangle).cz
//		SET OBJECT WIREFRAME current_triangle,1
//		ENDIF
//	mouse_control(1.0)
//	TEXT 0,0,STR$(current_triangle)
//	SYNC
//	IF current_triangle=20 OR SPACEKEY() THEN EXIT
//LOOP


``make remainder of triangles
DO
	side_used=make_next_triangle()
	D3D_LINE3D new_triangle_data(1).ax,0.0,new_triangle_data(1).az,new_triangle_data(1).bx,0.0,new_triangle_data(1).bz,RGB(255,0,0),1
	D3D_LINE3D new_triangle_data(1).bx,0.0,new_triangle_data(1).bz,new_triangle_data(1).cx,0.0,new_triangle_data(1).cz,RGB(0,255,0),1
	D3D_LINE3D new_triangle_data(1).cx,0.0,new_triangle_data(1).cz,new_triangle_data(1).ax,0.0,new_triangle_data(1).az,RGB(0,0,255),0
	
	IF check_if_valid()=0
		make_intersection_points()
		INC current_triangle
		copy_new_to_triangle_list()
		MAKE OBJECT TRIANGLE current_triangle,triangle_data(current_triangle).ax,0,triangle_data(current_triangle).az,triangle_data(current_triangle).bx,0,triangle_data(current_triangle).bz,triangle_data(current_triangle).cx,0,triangle_data(current_triangle).cz
		SET OBJECT WIREFRAME current_triangle,1
		triangle_data(current_triangle).ca_used=1
		SELECT side_used
			CASE 0
				triangle_data(triangle_to_use).ab_used=1
			ENDCASE
			CASE 1
				triangle_data(triangle_to_use).bc_used=1
			ENDCASE
			CASE 2
				triangle_data(triangle_to_use).ca_used=1
			ENDCASE
		ENDSELECT
	ENDIF
	mouse_control(1.0)
	TEXT 0,0,"map genertion -"+STR$(current_triangle)+" out of "+str$(max_triangles)
	IF INKEY$()="p"
		IF IMAGE EXIST(4)
			DELETE IMAGE 4
		ENDIF
		GET IMAGE 4,0,0,1024,768
		SAVE IMAGE "generation.jpg",4
	ENDIF
	SYNC
//	WAIT KEY
//	WAIT 50
	IF current_triangle=max_triangles OR SPACEKEY() THEN EXIT
LOOP

turn_data_into_map()
SYNC RATE 60	
POSITION CAMERA 0,0,0
POINT CAMERA 0,0,0
`*********************************
`main loop starts here
MAKE LIGHT 1
SET AMBIENT LIGHT 0
DO
	IF INKEY$()="p"
		IF IMAGE EXIST(4)
			DELETE IMAGE 4
		ENDIF
		GET IMAGE 4,0,0,1024,768
		SAVE IMAGE "level.jpg",4
	ENDIF
	mouse_control(1.0)
	SYNC
LOOP

`*********************************
`functions start here
FUNCTION mouse_control(speed AS FLOAT)
	XROTATE CAMERA CAMERA ANGLE X()+MOUSEMOVEY()
	YROTATE CAMERA CAMERA ANGLE Y()+MOUSEMOVEX()
	IF MOUSECLICK()=1 THEN MOVE CAMERA speed
	IF MOUSECLICK()=2 THEN MOVE CAMERA (0-speed)
	dummy=MOUSEMOVEX()
	dummy=MOUSEMOVEY()
ENDFUNCTION

FUNCTION point_in_triangle(px#,pz#,tri_x1#,tri_z1#,tri_x2#,tri_z2#,tri_x3#,tri_z3#)
	ret=0
	SET VECTOR3 point1,px#,0.0,pz#
	SET VECTOR3 point2,tri_x1#,0.0,tri_z1#
	SET VECTOR3 point3,tri_x2#,0.0,tri_z2#
	SET VECTOR3 point4,tri_x3#,0.0,tri_z3#
	IF same_side(point1,point2,point3,point4) AND same_side(point1,point3,point2,point4) AND same_side(point1,point4,point2,point3)
		ret=1
	ENDIF
ENDFUNCTION ret

FUNCTION same_side(p1,p2,a,b)
	ret=0
	SUBTRACT VECTOR3 result1,b,a
	SUBTRACT VECTOR3 result2,p1,a
	CROSS PRODUCT VECTOR3 result3,result1,result2
	SUBTRACT VECTOR3 result4,b,a
	SUBTRACT VECTOR3 result5,p2,a
	CROSS PRODUCT VECTOR3 result6,result4,result5
	IF DOT PRODUCT VECTOR3(result3,result6)>=0.1 THEN ret=1
ENDFUNCTION ret

FUNCTION make_new_triangle
	new_triangle_data(1).ax=RND(triangle_size/2.0)*-1.0-1.0
	new_triangle_data(1).az=RND(triangle_size/2.0)*-1.0-1.0
	
	new_triangle_data(1).bx=0.0
	new_triangle_data(1).bz=RND(triangle_size/2.0)+1.0
	
	new_triangle_data(1).cx=RND(triangle_size/2.0)+1.0
	new_triangle_data(1).cz=RND(triangle_size/2.0)*-1.0-1.0	
	make_intersection_points()
ENDFUNCTION

FUNCTION move_triangle()
	x#=RND(300.0)-150.0
	z#=RND(300.0)-150.0
	new_triangle_data(1).ax=new_triangle_data(1).ax+x#
	new_triangle_data(1).az=new_triangle_data(1).az+z#
	
	new_triangle_data(1).bx=new_triangle_data(1).bx+x#
	new_triangle_data(1).bz=new_triangle_data(1).bz+z#
	
	new_triangle_data(1).cx=new_triangle_data(1).cx+x#
	new_triangle_data(1).cz=new_triangle_data(1).cz+z#
ENDFUNCTION

FUNCTION copy_new_to_triangle_list()
	triangle_data(current_triangle).ax=new_triangle_data(1).ax
	triangle_data(current_triangle).az=new_triangle_data(1).az
	
	triangle_data(current_triangle).bx=new_triangle_data(1).bx
	triangle_data(current_triangle).bz=new_triangle_data(1).bz
	
	triangle_data(current_triangle).cx=new_triangle_data(1).cx
	triangle_data(current_triangle).cz=new_triangle_data(1).cz
	
	
ENDFUNCTION

FUNCTION check_if_valid()
	test=0
	FOR l=1 TO current_triangle
		INC test,point_in_triangle(new_triangle_data(1).ax,new_triangle_data(1).az,triangle_data(l).ax,triangle_data(l).az,triangle_data(l).bx,triangle_data(l).bz,triangle_data(l).cx,triangle_data(l).cz)	
		INC test,point_in_triangle(new_triangle_data(1).bx,new_triangle_data(1).bz,triangle_data(l).ax,triangle_data(l).az,triangle_data(l).bx,triangle_data(l).bz,triangle_data(l).cx,triangle_data(l).cz)	
		INC test,point_in_triangle(new_triangle_data(1).cx,new_triangle_data(1).cz,triangle_data(l).ax,triangle_data(l).az,triangle_data(l).bx,triangle_data(l).bz,triangle_data(l).cx,triangle_data(l).cz)	
	
		INC test,point_in_triangle(triangle_data(l).ax,triangle_data(l).az,new_triangle_data(1).ax,new_triangle_data(1).az,new_triangle_data(1).bx,new_triangle_data(1).bz,new_triangle_data(1).cx,new_triangle_data(1).cz)	
		INC test,point_in_triangle(triangle_data(l).bx,triangle_data(l).bz,new_triangle_data(1).ax,new_triangle_data(1).az,new_triangle_data(1).bx,new_triangle_data(1).bz,new_triangle_data(1).cx,new_triangle_data(1).cz)	
		INC test,point_in_triangle(triangle_data(l).cx,triangle_data(l).cz,new_triangle_data(1).ax,new_triangle_data(1).az,new_triangle_data(1).bx,new_triangle_data(1).bz,new_triangle_data(1).cx,new_triangle_data(1).cz)	
	
		``ab to ab
		INC test,line_intersect(new_triangle_data(1).ax,new_triangle_data(1).az,new_triangle_data(1).bx,new_triangle_data(1).bz,triangle_data(l).ax,triangle_data(l).az,triangle_data(l).bx,triangle_data(l).bz)
		``ab to ac
		INC test,line_intersect(new_triangle_data(1).ax,new_triangle_data(1).az,new_triangle_data(1).bx,new_triangle_data(1).bz,triangle_data(l).ax,triangle_data(l).az,triangle_data(l).cx,triangle_data(l).cz)
		``ab to bc
		INC test,line_intersect(new_triangle_data(1).ax,new_triangle_data(1).az,new_triangle_data(1).bx,new_triangle_data(1).bz,triangle_data(l).bx,triangle_data(l).bz,triangle_data(l).cx,triangle_data(l).cz)
		
		``ac to ab
		INC test,line_intersect(new_triangle_data(1).ax,new_triangle_data(1).az,new_triangle_data(1).cx,new_triangle_data(1).cz,triangle_data(l).ax,triangle_data(l).az,triangle_data(l).bx,triangle_data(l).bz)
		``ac to ac
		INC test,line_intersect(new_triangle_data(1).ax,new_triangle_data(1).az,new_triangle_data(1).cx,new_triangle_data(1).cz,triangle_data(l).ax,triangle_data(l).az,triangle_data(l).cx,triangle_data(l).cz)
		``ac to bc
		INC test,line_intersect(new_triangle_data(1).ax,new_triangle_data(1).az,new_triangle_data(1).cx,new_triangle_data(1).cz,triangle_data(l).bx,triangle_data(l).bz,triangle_data(l).cx,triangle_data(l).cz)
		
		``bc to ab
		INC test,line_intersect(new_triangle_data(1).bx,new_triangle_data(1).bz,new_triangle_data(1).cx,new_triangle_data(1).cz,triangle_data(l).ax,triangle_data(l).az,triangle_data(l).bx,triangle_data(l).bz)
		``bc to ac
		INC test,line_intersect(new_triangle_data(1).bx,new_triangle_data(1).bz,new_triangle_data(1).cx,new_triangle_data(1).cz,triangle_data(l).ax,triangle_data(l).az,triangle_data(l).cx,triangle_data(l).cz)
		``bc to bc
		INC test,line_intersect(new_triangle_data(1).bx,new_triangle_data(1).bz,new_triangle_data(1).cx,new_triangle_data(1).cz,triangle_data(l).bx,triangle_data(l).bz,triangle_data(l).cx,triangle_data(l).cz)
	
		IF triangle_data(l).ax=new_triangle_data(1).ax AND triangle_data(l).az=new_triangle_data(1).az
			IF triangle_data(l).bx=new_triangle_data(1).bx AND triangle_data(l).bz=new_triangle_data(1).bz
				IF triangle_data(l).cx=new_triangle_data(1).cx AND triangle_data(l).cz=new_triangle_data(1).cz
					INC test
				ENDIF
			ENDIF
		ENDIF
		IF triangle_data(l).bx=new_triangle_data(1).bx AND triangle_data(l).az=new_triangle_data(1).az
			IF triangle_data(l).cx=new_triangle_data(1).cx AND triangle_data(l).bz=new_triangle_data(1).bz
				IF triangle_data(l).ax=new_triangle_data(1).ax AND triangle_data(l).cz=new_triangle_data(1).cz
					INC test
				ENDIF
			ENDIF
		ENDIF
		IF triangle_data(l).cx=new_triangle_data(1).cx AND triangle_data(l).az=new_triangle_data(1).az
			IF triangle_data(l).ax=new_triangle_data(1).ax AND triangle_data(l).bz=new_triangle_data(1).bz
				IF triangle_data(l).bx=new_triangle_data(1).bx AND triangle_data(l).cz=new_triangle_data(1).cz
					INC test
				ENDIF
			ENDIF
		ENDIF
	
	NEXT l
ENDFUNCTION test

FUNCTION make_intersection_points()
	``ab
	POSITION OBJECT dummy_ab,new_triangle_data(1).bx,0.0,new_triangle_data(1).bz
	POINT OBJECT dummy_ab,new_triangle_data(1).ax,0.0,new_triangle_data(1).az
	dist#=distance_3d(new_triangle_data(1).ax,0.0,new_triangle_data(1).az,new_triangle_data(1).bx,0.0,new_triangle_data(1).bz)
	intersect_data(1).ab_dist=dist#
	MOVE OBJECT dummy_ab,RND(dist#)
	YROTATE OBJECT dummy_ab,WRAPVALUE(OBJECT ANGLE Y(dummy_ab)+90.0)
	MOVE OBJECT dummy_ab,1.0
	``sorts out if left or ight handed triangle then intersect is all ways on outside
	IF point_in_triangle(OBJECT POSITION X(dummy_ab),OBJECT POSITION Z(dummy_ab),new_triangle_data(1).ax,new_triangle_data(1).az,new_triangle_data(1).bx,new_triangle_data(1).bz,new_triangle_data(1).cx,new_triangle_data(1).cz)
		MOVE OBJECT dummy_ab,(RND(dist#)+2.0)*-1.0
	ELSE
		MOVE OBJECT dummy_ab,RND(dist#)
	ENDIF
	intersect_data(1).ab_x=OBJECT POSITION X(dummy_ab)
	intersect_data(1).ab_z=OBJECT POSITION Z(dummy_ab)
	
	``bc
	POSITION OBJECT dummy_bc,new_triangle_data(1).cx,0.0,new_triangle_data(1).cz
	POINT OBJECT dummy_bc,new_triangle_data(1).bx,0.0,new_triangle_data(1).bz
	dist#=distance_3d(new_triangle_data(1).bx,0.0,new_triangle_data(1).bz,new_triangle_data(1).cx,0.0,new_triangle_data(1).cz)
	intersect_data(1).bc_dist=dist#
	MOVE OBJECT dummy_bc,RND(dist#)
	YROTATE OBJECT dummy_bc,WRAPVALUE(OBJECT ANGLE Y(dummy_bc)+90.0)
	MOVE OBJECT dummy_bc,1.0
	``sorts out if left or ight handed triangle then intersect is all ways on outside
	IF point_in_triangle(OBJECT POSITION X(dummy_bc),OBJECT POSITION Z(dummy_bc),new_triangle_data(1).ax,new_triangle_data(1).az,new_triangle_data(1).bx,new_triangle_data(1).bz,new_triangle_data(1).cx,new_triangle_data(1).cz)
		MOVE OBJECT dummy_bc,(RND(dist#)+2.0)*-1.0
	ELSE
		MOVE OBJECT dummy_bc,RND(dist#)
	ENDIF
	intersect_data(1).bc_x=OBJECT POSITION X(dummy_bc)
	intersect_data(1).bc_z=OBJECT POSITION Z(dummy_bc)
	
	``ca
	POSITION OBJECT dummy_ca,new_triangle_data(1).ax,0.0,new_triangle_data(1).az
	POINT OBJECT dummy_ca,new_triangle_data(1).cx,0.0,new_triangle_data(1).cz
	dist#=distance_3d(new_triangle_data(1).cx,0.0,new_triangle_data(1).cz,new_triangle_data(1).ax,0.0,new_triangle_data(1).az)
	intersect_data(1).ca_dist=dist#
	MOVE OBJECT dummy_ca,RND(dist#)
	YROTATE OBJECT dummy_ca,WRAPVALUE(OBJECT ANGLE Y(dummy_ca)+90.0)
	MOVE OBJECT dummy_ca,1.0
	``sorts out if left or ight handed triangle then intersect is all ways on outside
	IF point_in_triangle(OBJECT POSITION X(dummy_ca),OBJECT POSITION Z(dummy_ca),new_triangle_data(1).ax,new_triangle_data(1).az,new_triangle_data(1).bx,new_triangle_data(1).bz,new_triangle_data(1).cx,new_triangle_data(1).cz)
		MOVE OBJECT dummy_ca,(RND(dist#)+2.0)*-1.0
	ELSE
		MOVE OBJECT dummy_ca,RND(dist#)
	ENDIF
	intersect_data(1).ca_x=OBJECT POSITION X(dummy_ca)
	intersect_data(1).ca_z=OBJECT POSITION Z(dummy_ca)
	
ENDFUNCTION

FUNCTION distance_3d( x1# AS FLOAT, y1# AS FLOAT, z1# AS FLOAT, x2# AS FLOAT, y2# AS FLOAT, z2# AS FLOAT )
   distance# = ABS(SQRT((x1# - x2#) ^ 2 + (y1# - y2#) ^ 2 + (z1# - z2#) ^ 2))
ENDFUNCTION distance#

FUNCTION make_next_triangle()

	triangle_to_use=RND(current_triangle)
	IF triangle_to_use<1
		triangle_to_use=1
	ENDIF
	copy_triangle_to_new_list(triangle_to_use)
	make_intersection_points()
	side_to_use=RND(2)
	SELECT side_to_use
		``ab
		CASE 0
			new_triangle_data(1).ax=triangle_data(triangle_to_use).ax
			new_triangle_data(1).az=triangle_data(triangle_to_use).az
				
			new_triangle_data(1).cx=triangle_data(triangle_to_use).bx
			new_triangle_data(1).cz=triangle_data(triangle_to_use).bz
				
			new_triangle_data(1).bx=intersect_data(1).ab_x
			new_triangle_data(1).bz=intersect_data(1).ab_z
		ENDCASE
		
		``bc
		CASE 1
			new_triangle_data(1).ax=triangle_data(triangle_to_use).bx
			new_triangle_data(1).az=triangle_data(triangle_to_use).bz
				
			new_triangle_data(1).cx=triangle_data(triangle_to_use).cx
			new_triangle_data(1).cz=triangle_data(triangle_to_use).cz
				
			new_triangle_data(1).bx=intersect_data(1).bc_x
			new_triangle_data(1).bz=intersect_data(1).bc_z
		ENDCASE
		
		``ca
		CASE 2
			new_triangle_data(1).ax=triangle_data(triangle_to_use).cx
			new_triangle_data(1).az=triangle_data(triangle_to_use).cz
				
			new_triangle_data(1).cx=triangle_data(triangle_to_use).ax
			new_triangle_data(1).cz=triangle_data(triangle_to_use).az
				
			new_triangle_data(1).bx=intersect_data(1).ca_x
			new_triangle_data(1).bz=intersect_data(1).ca_z
		ENDCASE

	ENDSELECT
		
ENDFUNCTION side_to_use

FUNCTION copy_triangle_to_new_list(use)
	new_triangle_data(1).ax=triangle_data(use).ax
	new_triangle_data(1).az=triangle_data(use).az
	
	new_triangle_data(1).bx=triangle_data(use).bx
	new_triangle_data(1).bz=triangle_data(use).bz
	
	new_triangle_data(1).cx=triangle_data(use).cx
	new_triangle_data(1).cz=triangle_data(use).cz
ENDFUNCTION

``thanks whoever did this bit of code works great
FUNCTION line_intersect(x1#,y1#,x2#,y2#,x3#,y3#,x4#,y4#)
   denominator# = ((y4# - y3#)*(x2# - x1#)) - ((x4# - x3#)*(y2# - y1#))
   IF denominator# <> 0
      numerator# = ((x4# - x3#)*(y1# - y3#)) - ((y4# - y3#)*(x1# - x3#))
      uA# = numerator# / denominator#
      numerator# = ((x2# - x1#)*(y1# - y3#)) - ((y2# - y1#)*(x1# - x3#))
      uB# = numerator# / denominator#
      IF (uA# > 0) AND (uA# < 1) AND (uB# > 0) AND (uB# < 1)
         collision = 1
      ELSE
         collision = 0
      ENDIF
   ELSE
      collision = 0
   ENDIF
ENDFUNCTION collision

``*******************************************************************
``turn all the data into a 3d level
``*******************************************************************
FUNCTION turn_data_into_map()
	
	``delete all current objects
	DELETE OBJECT dummy_ab
	DELETE OBJECT dummy_bc
	DELETE OBJECT dummy_ca
	FOR l=1 TO max_triangles
		delete object l
	NEXT l
	
	``find min & max
	min_x#=10000.0
	min_z#=10000.0
	max_x#=-10000.0
	max_z#=-10000.0
	FOR l=1 TO max_triangles
		IF triangle_data(l).ax<min_x#
			min_x#=triangle_data(l).ax
		ENDIF
		IF triangle_data(l).bx<min_x#
			min_x#=triangle_data(l).bx
		ENDIF
		IF triangle_data(l).cx<min_x#
			min_x#=triangle_data(l).cx
		ENDIF
		
		IF triangle_data(l).az<min_z#
			min_z#=triangle_data(l).az
		ENDIF
		IF triangle_data(l).bz<min_z#
			min_z#=triangle_data(l).bz
		ENDIF
		IF triangle_data(l).cz<min_z#
			min_z#=triangle_data(l).cz
		ENDIF
		
		IF triangle_data(l).ax>max_x#
			max_x#=triangle_data(l).ax
		ENDIF
		IF triangle_data(l).bx>max_x#
			max_x#=triangle_data(l).bx
		ENDIF
		IF triangle_data(l).cx>max_x#
			max_x#=triangle_data(l).cx
		ENDIF
		
		IF triangle_data(l).az>maz_z#
			max_z#=triangle_data(l).az
		ENDIF
		IF triangle_data(l).bz>maz_z#
			max_z#=triangle_data(l).bz
		ENDIF
		IF triangle_data(l).cz>maz_z#
			max_z#=triangle_data(l).cz
		ENDIF
	NEXT l
	ustep#=1.0/(max_x#-min_x#)
	vstep#=1.0/(max_z#-min_z#)
	
	create_memblockobject(1,max_triangles*3)
	``floor
	vertex=0
	FOR l=1 TO max_triangles
		create_vertex(1,vertex,triangle_data(l).ax,-5.0,triangle_data(l).az,0,(triangle_data(l).ax+min_x#)*ustep#,(triangle_data(l).az+min_z#)*vstep#)
		set_normal(1,vertex,0,1,0)
		INC vertex
		create_vertex(1,vertex,triangle_data(l).bx,-5.0,triangle_data(l).bz,0,(triangle_data(l).bx+min_x#)*ustep#,(triangle_data(l).bz+min_z#)*vstep#)
		set_normal(1,vertex,0,1,0)
		INC vertex
		create_vertex(1,vertex,triangle_data(l).cx,-5.0,triangle_data(l).cz,0,(triangle_data(l).cx+min_x#)*ustep#,(triangle_data(l).cz+min_z#)*vstep#)
		set_normal(1,vertex,0,1,0)
		INC vertex
	NEXT l
	make_object(1,1,1,0)
	SET OBJECT NORMALS 1
	TEXTURE OBJECT 1,3
	SCALE OBJECT TEXTURE 1,20,20
	``COLOR OBJECT 1,RGB(255,0,0)
	``set object wireframe 1,1
	
	``ceiling
	vertex=0
	FOR l=1 TO max_triangles
		create_vertex(1,vertex,triangle_data(l).cx,5.0,triangle_data(l).cz,0,(triangle_data(l).ax+min_x#)*ustep#,(triangle_data(l).az+min_z#)*vstep#)
		set_normal(1,vertex,0,1,0)
		INC vertex
		create_vertex(1,vertex,triangle_data(l).bx,5.0,triangle_data(l).bz,0,(triangle_data(l).bx+min_x#)*ustep#,(triangle_data(l).bz+min_z#)*vstep#)
		set_normal(1,vertex,0,1,0)
		INC vertex
		create_vertex(1,vertex,triangle_data(l).ax,5.0,triangle_data(l).az,0,(triangle_data(l).cx+min_x#)*ustep#,(triangle_data(l).cz+min_z#)*vstep#)
		set_normal(1,vertex,0,1,0)
		INC vertex
	NEXT l
	make_object(2,1,1,0)
	SET OBJECT NORMALS 2
	TEXTURE OBJECT 2,2
	SCALE OBJECT TEXTURE 2,20,20
	``COLOR OBJECT 2,RGB(0,255,0)
	``SET OBJECT WIREFRAME 2,1
	
	``walls
	``find number of edges
	num_edges=0
	FOR l=1 TO max_triangles
		IF triangle_data(l).ab_used=0
			INC num_edges
		ENDIF
		IF triangle_data(l).bc_used=0
			inc num_edges
		ENDIF
		IF triangle_data(l).ca_used=0
			INC num_edges
		ENDIF
	NEXT l
	DELETE MEMBLOCK 1
	create_memblockobject(1,num_edges*2*3)
	vertex=0
	FOR l=1 TO max_triangles
		
		IF triangle_data(l).ab_used=0
			create_vertex(1,vertex,triangle_data(l).ax,-5.0,triangle_data(l).az,0,0.0,0.0)
			set_normal(1,vertex,1,0,0)
			INC vertex
			create_vertex(1,vertex,triangle_data(l).ax,5.0,triangle_data(l).az,0,0.0,1.0)
			set_normal(1,vertex,1,0,0)
			INC vertex
			create_vertex(1,vertex,triangle_data(l).bx,-5.0,triangle_data(l).bz,0,1.0,0.0)
			set_normal(1,vertex,1,0,0)
			INC vertex
			
			create_vertex(1,vertex,triangle_data(l).bx,-5.0,triangle_data(l).bz,0,1.0,0.0)
			set_normal(1,vertex,1,0,0)
			INC vertex
			create_vertex(1,vertex,triangle_data(l).ax,5.0,triangle_data(l).az,0,0.0,1.0)
			set_normal(1,vertex,1,0,0)
			INC vertex
			create_vertex(1,vertex,triangle_data(l).bx,5.0,triangle_data(l).bz,0,1.0,1.0)
			set_normal(1,vertex,1,0,0)
			INC vertex
		ENDIF
		IF triangle_data(l).bc_used=0
			create_vertex(1,vertex,triangle_data(l).bx,-5.0,triangle_data(l).bz,0,0.0,0.0)
			set_normal(1,vertex,1,0,0)
			INC vertex
			create_vertex(1,vertex,triangle_data(l).bx,5.0,triangle_data(l).bz,0,0.0,1.0)
			set_normal(1,vertex,1,0,0)
			INC vertex
			create_vertex(1,vertex,triangle_data(l).cx,-5.0,triangle_data(l).cz,0,1.0,0.0)
			set_normal(1,vertex,1,0,0)
			INC vertex
			
			create_vertex(1,vertex,triangle_data(l).cx,-5.0,triangle_data(l).cz,0,1.0,0.0)
			set_normal(1,vertex,1,0,0)
			INC vertex
			create_vertex(1,vertex,triangle_data(l).bx,5.0,triangle_data(l).bz,0,0.0,1.0)
			set_normal(1,vertex,1,0,0)
			INC vertex
			create_vertex(1,vertex,triangle_data(l).cx,5.0,triangle_data(l).cz,0,1.0,1.0)
			set_normal(1,vertex,1,0,0)
			INC vertex
		ENDIF
		IF triangle_data(l).ca_used=0
			create_vertex(1,vertex,triangle_data(l).cx,-5.0,triangle_data(l).cz,0,0.0,0.0)
			set_normal(1,vertex,1,0,0)
			INC vertex
			create_vertex(1,vertex,triangle_data(l).cx,5.0,triangle_data(l).cz,0,0.0,1.0)
			set_normal(1,vertex,1,0,0)
			INC vertex
			create_vertex(1,vertex,triangle_data(l).ax,-5.0,triangle_data(l).az,0,1.0,0.0)
			set_normal(1,vertex,1,0,0)
			INC vertex
			
			create_vertex(1,vertex,triangle_data(l).ax,-5.0,triangle_data(l).az,0,1.0,0.0)
			set_normal(1,vertex,1,0,0)
			INC vertex
			create_vertex(1,vertex,triangle_data(l).cx,5.0,triangle_data(l).cz,0,0.0,1.0)
			set_normal(1,vertex,1,0,0)
			INC vertex
			create_vertex(1,vertex,triangle_data(l).ax,5.0,triangle_data(l).az,0,1.0,1.0)
			set_normal(1,vertex,1,0,0)
			INC vertex
		ENDIF
		
	NEXT l
	make_object(3,1,1,0)
	SET OBJECT NORMALS 3
	TEXTURE OBJECT 3,1
	``COLOR OBJECT 3,RGB(0,0,255)
	``SET OBJECT WIREFRAME 3,1
ENDFUNCTION




FUNCTION create_memblockobject(memnum,v)
	MAKE MEMBLOCK memnum,12+(32*v)
   WRITE MEMBLOCK DWORD memnum,0,274
   WRITE MEMBLOCK DWORD memnum,4,32
   WRITE MEMBLOCK DWORD memnum,8,v
ENDFUNCTION

FUNCTION create_vertex(memnum,v,vposx#,vposy#,vposz#,color AS DWORD,u#,v#)
	WRITE MEMBLOCK FLOAT memnum,v*32+12,vposx#
   WRITE MEMBLOCK FLOAT memnum,v*32+16,vposy#
   WRITE MEMBLOCK FLOAT memnum,v*32+20,vposz#
   ``write memblock dword memnum,v*36+36,color `not needed in 274fvf format diffuse color seems to mess up some shader code as well
   WRITE MEMBLOCK FLOAT memnum,v*32+36,u#
   WRITE MEMBLOCK FLOAT memnum,v*32+40,v#
ENDFUNCTION

FUNCTION set_normal(memnum,v,normalx#,normaly#,normalz#)
	WRITE MEMBLOCK FLOAT memnum,v*32+24,normalx#
   WRITE MEMBLOCK FLOAT memnum,v*32+28,normaly#
   WRITE MEMBLOCK FLOAT memnum,v*32+32,normalz#
ENDFUNCTION

FUNCTION make_object(objnum,meshnum,memnum,imgnum)
	IF OBJECT EXIST (objnum) THEN DELETE OBJECT objnum
	IF MESH EXIST (meshnum) THEN DELETE MESH meshnum
   MAKE MESH FROM MEMBLOCK meshnum,memnum
   MAKE OBJECT objnum,meshnum,imgnum
ENDFUNCTION

void MAP_DATA::create_floor_object() {
	int		obj = free_obj();
	int		loop;

	M1U_MakeObjectNew( obj, verts.size(), faces.size() * 3 );

	dbLockVertexBufferForLimb( obj, 0 );

	// convert verts to 3d coords
	for ( loop = 0; loop < (int)verts.size(); loop++ ) {
		dbSetVertexPosition( loop, verts[ loop ].x, 0.0f, verts[ loop ].y );

		dbSetVertexUV( loop, 
			fmod( verts[ loop ].x / edge_length, edge_length ) ,
			fmod( verts[ loop ].y / edge_length, edge_length ) );
	}

	// create each of the triangle faces
	for ( loop = 0; loop < (int)faces.size(); loop++ ) {
		dbSetVertexIndexData( loop * 3 + 0, faces[ loop ].v1 );
		dbSetVertexIndexData( loop * 3 + 2, faces[ loop ].v2 );
		dbSetVertexIndexData( loop * 3 + 1, faces[ loop ].v3 );
	}

	dbUnlockVertexBuffer();
	dbCalculateObjectBounds( obj );
	dbSetObjectNormals( obj );

	floorObjID = obj;
}

void MAP_DATA::create_roof_object() {
	int		obj = free_obj();
	int		loop;

	M1U_MakeObjectNew( obj, verts.size(), faces.size() * 3 );

	dbLockVertexBufferForLimb( obj, 0 );

	// convert verts to 3d coords
	for ( loop = 0; loop < (int)verts.size(); loop++ ) {
		dbSetVertexPosition( loop, verts[ loop ].x, edge_length, verts[ loop ].y );

		dbSetVertexUV( loop, 
			fmod( verts[ loop ].x / edge_length, edge_length ) ,
			fmod( verts[ loop ].y / edge_length, edge_length ) );
	}

	// create each of the triangle faces
	for ( loop = 0; loop < (int)faces.size(); loop++ ) {
		dbSetVertexIndexData( loop * 3 + 0, faces[ loop ].v1 );
		dbSetVertexIndexData( loop * 3 + 1, faces[ loop ].v2 );
		dbSetVertexIndexData( loop * 3 + 2, faces[ loop ].v3 );
	}

	dbUnlockVertexBuffer();
	dbCalculateObjectBounds( obj );
	dbSetObjectNormals( obj );

	roofObjID = obj;
}

void MAP_DATA::create_wall_object() {
	int		obj = free_obj();
	int		loop;
	int		vert2;	// halfway mark for upper vertices

	vert2 = verts.size();

	M1U_MakeObjectNew( obj, vert2 * 2, outer.size() * 6 );

	dbLockVertexBufferForLimb( obj, 0 );

	for ( loop = 0; loop < (int)verts.size(); loop++ ) {
		dbSetVertexPosition( loop, verts[ loop ].x, 0.0f, verts[ loop ].y );
		dbSetVertexPosition( loop + vert2, verts[ loop ].x, edge_length, verts[ loop ].y );

		dbSetVertexUV( loop, 
			fmod( (float)loop, 2.0f ) ,
			fmod( (float)( loop + 1 ), 2.0f ) );
		dbSetVertexUV( loop + vert2, 
			fmod( (float)(loop+vert2), 2.0f ) ,
			fmod( (float)(loop+vert2), 2.0f ) );
	}

	for ( loop = 0; loop < (int)outer.size(); loop++ ) {
		int lower_start	= outer[loop].start;
		int lower_end	= outer[loop].end;
		int upper_start	= lower_start + vert2;
		int upper_end	= lower_end + vert2;

		dbSetVertexIndexData( loop * 6 + 0, lower_start );
		dbSetVertexIndexData( loop * 6 + 1, upper_end );
		dbSetVertexIndexData( loop * 6 + 2, upper_start );

		dbSetVertexIndexData( loop * 6 + 3, upper_end );
		dbSetVertexIndexData( loop * 6 + 4, lower_start );
		dbSetVertexIndexData( loop * 6 + 5, lower_end );
	}

	dbUnlockVertexBuffer();
	dbCalculateObjectBounds( obj );
	dbSetObjectNormals( obj );

	wallObjID = obj;
}

void MAP_DATA::create_wall_object() {
	// setup the array for the wall edges
	vector<_EDGE> walls;

	// push first edge into the list (from now on we can ignore outer[0])
	walls.push_back( _EDGE( outer[0].start, outer[0].end ) );

	// we're looking for this in the edge arrays 'start' index
	int		look = outer[0].end;
	int		outer_size = (int)outer.size();	// optimise the search algorithm
	int		walls_size = 1;					// ditto

	while ( walls_size < outer_size ) { 
		int	curr_edge = 1;
		int vfound;							// ditto

		// okay this bit ain't cache friendly
		while ( outer[ curr_edge ].start != look ) {
			curr_edge++; }

		// push the new edge info
		vfound = outer[ curr_edge ].end;
		walls.push_back( _EDGE( look, vfound ) );

		// set the new looking for vertex index
		look = vfound;

		// increment the array size
		walls_size++;

	} // EOF while ( walls.size() < outer_size )

	// the above sort algorithm has already been optimised to use local
	// variables which means cache friendly were possible

	// Now we can sort the UV coords for each vertex

	// First of all before we start, create the object (might help)
	int obj = free_obj();

	int vert2 = verts.size();

	M1U_MakeObjectNew( obj, vert2 * 2, outer.size() * 6 );

	dbLockVertexBufferForLimb( obj, 0 );

	// store the upper and lower vertices
	int loop;
	
	for ( loop = 0; loop < vert2; loop++ ) {
		dbSetVertexPosition(loop		,verts[loop].x, 0.0f,		 verts[loop].y);
		dbSetVertexPosition(loop+vert2	,verts[loop].x, edge_length, verts[loop].y);
	}

	// store the first UV data for the first vertex in the walls list
	dbSetVertexUV( walls[0].start,		   0.0f, 0.0f );
	dbSetVertexUV( walls[0].start + vert2, 0.0f, 1.0f );

	int		UVindex = 1;		// Now for the next vertex UV coords
	float	currUV	= 0;		// this will wrap UV's round the walls

	// UV index will from now on be calulated from each edges end vertex

	// get the edges start coords (used to calc edge length)
	int		start = walls[0].start;
	int		end;
	float	x1 = verts[ start ].x;
	float	y1 = verts[ start ].y;

	// declare these vars for length calc
	float x2,y2,length;

	// create the 2 triangle faces for each edge and set end vert UV
	for ( loop = 0; loop < vert2; loop++) {
		end = walls[ loop ].end;
		x2 = verts[ end ].x;
		y2 = verts[ end ].y;
		length = fabs( sqrt((x2-x1)*(x2-x1) + (y2-y1)*(y2-y1)) );
		currUV += length / edge_length;
		dbSetVertexUV( end,			currUV, 0.0f );
		dbSetVertexUV( end + vert2, currUV, 1.0f );

		// now create the two faces
		dbSetVertexIndexData( loop * 6 + 0, start );
		dbSetVertexIndexData( loop * 6 + 1, end + vert2 );
		dbSetVertexIndexData( loop * 6 + 2, start + vert2 );

		dbSetVertexIndexData( loop * 6 + 3, start );
		dbSetVertexIndexData( loop * 6 + 4, end );
		dbSetVertexIndexData( loop * 6 + 5, end + vert2 );

		x1 = x2; y1 = y2; start = end;
	}

	dbUnlockVertexBuffer();
	dbCalculateObjectBounds( obj );
	dbSetObjectNormals( obj );

	wallObjID = obj;
}

void MAP_DATA::load_map_decs() {
	int		obj;
	// decObj[0] = wall light
	decObj.push_back( obj = dbLoadObject( "decs/dec_light.X" ) ); dbHideObject( obj );
}

void MAP_DATA::decs_wall_lights() {
	int		osize	= outer.size();
	int		amt		= osize >> 1;		// 1/2 of edges will have wall lights
	char	*edges = new char[ osize ];	// flags for each outer edge
	int		loop;
	int		rnd;

	// zero all flags
	for ( loop = 0; loop < osize; loop++ ) edges[ loop ] = 0;

	while ( amt ) {
		// find an edge with a 0 flag set
		if ( edges[ rnd = ( rand() % osize ) ] == 0 ) {

			float	center_x, center_y, angle;
			int		obj;

			// set edges flag to 1
			edges[ rnd ] = 1;

			// get center coords and angle of the edge
			get_outer_edge( rnd, & center_x, & center_y, &angle );

			// convert to degrees
			angle = 360.0f - ( angle * ( 180.0f / PI ) );

			// instance the wall light and place it
			obj = dbInstanceObject( decObj[0] );
			dbPositionObject( obj, center_x, edge_length * 0.75f, center_y );
			dbYRotateObject( obj, angle );

			// decrement the counter
			amt--;
		}
	}

	delete[] edges;
}

void MAP_DATA::get_outer_edge(int e, float *cx, float *cy, float *ang) {
	*cx = ( verts[ outer[e].start ].x + verts[ outer[e].end ].x ) / 2.0f;
	*cy = ( verts[ outer[e].start ].y + verts[ outer[e].end ].y ) / 2.0f;

	*ang = atan2( verts[ outer[e].end ].y - verts[ outer[e].start ].y,
				  verts[ outer[e].end ].x - verts[ outer[e].start ].x );
}

outsize = array count( _OUT() )
        if outsize < 10
            edge = outsize - rnd( 1 )
        else
            edge = outsize - ( rnd( outsize ) * 12 ) / 100
        endif

outsize = array count( _OUT() )
        if outsize < 10
            edge = outsize - rnd( 1 )
        else
            edge = outsize - ( ( rnd( outsize ) * 12.0 ) / 100.0 )
        endif

trace_init("trace.txt")

init_screen()

MG_init()
MG_generate(0)
MG_create_level("","","")   ` don't load textures, generate some instead

init_controls()

position camera 0,500,0 : point camera 0,0,25

disable escapekey

while escapekey() = 0
    do_controls()
    if keystate(28)
        make_a_new_level()
    endif
    sync
endwhile

trace_close()

end



` ====================
` put this into a function to make the main() look dead tiny
function init_screen()
    autocam off
    sync rate 60
    sync on
    set display mode 1024,768,32
    set window off
endfunction

` ====================
` a failed attempt at getting a C fmod function working
` I've got the code working anyway by using the maps extents
` to make to passed values positive...
function fmodold(a as float,b as float)
    local v as float
    
    if a < 0
        a = abs( a )
        v = b - ( a - int( a / b ) * b )
    else
        v =     ( a - int( a / b ) * b )
    endif
endfunction v

function fmod(a#, b#)
    c#=a# %% b#
endfunction c#

` ====================
` my standard trace function while I'm debugging and getting everything working
function trace_init(file$)
    global WL_TRACE_FP as integer
    c as integer : c=1
    while ( c <= 32 and file open( c ) )
        inc c
    endwhile
    if ( c <= 32 )
        WL_TRACE_FP=c
    else
        exitfunction
    endif
    if ( file exist(file$) ) then delete file file$
    open to write WL_TRACE_FP,file$
    write string WL_TRACE_FP,"Trace file created : "+get date$()+", "+get time$()
    write string WL_TRACE_FP,"File handle used : "+str$(WL_TRACE_FP)
endfunction

function trace_close()
    write string WL_TRACE_FP,"EOF Trace file (safe program exit)"
    close file WL_TRACE_FP
endfunction

function trace_write(t$)
    write string WL_TRACE_FP,t$
endfunction

` ====================
` mouse and keyboard controls to free fly around to view the map
function init_controls()
    global objc as integer
    global objcsize as integer
    objcsize=30
    objc = find free object()
    make object sphere objc,objcsize
    position object objc,MG_center_x_in(0),objcsize,MG_center_y_in(0)
    lightc = find free light()
    make light lightc
    set spot light lightc, 5, 20
    set light range lightc, 1000

    ` players gravity and controls
    global pgrav# = 0.0
    global pground = 1
endfunction

function do_controls()
    mx# = mousemovex() / 4.0
    my# = mousemovey() / 4.0
    mc = mouseclick()
    
    yrotate object objc, wrapvalue(object angle y(objc) + mx#)
    xrotate object objc, wrapvalue(object angle x(objc) + my#)
    
    ox# = object position x(objc)
    oy# = object position y(objc)
    oz# = object position z(objc)
    
    if spacekey() and pground = 1
        pgrav# = 5.0
    endif
    if pgrav# > -2.0
        pgrav# = pgrav# - 0.35
        pground = 0
    endif
    
    position object objc, ox#, oy# + pgrav#, oz#
    move object objc, ( keystate(17) - keystate(31) ) * 5
    move object right objc, ( keystate(32) - keystate(30) ) * 5
    
    nx# = object position x(objc)
    ny# = object position y(objc)
    nz# = object position z(objc)
    
    c = sc_spherecastgroup( 1, ox#,oy#,oz#, nx#,ny#,nz#, objcsize,0 )
    
    if c
        nx# = sc_getcollisionslidex()
        ny# = sc_getcollisionslidey()
        nz# = sc_getcollisionslidez()
        position object objc, nx#, ny#, nz#
        if sc_getcollisionnormaly() > 0.5   ` hit ground?
            pground = 1
        endif
    endif
    
    position camera object position x(objc), object position y(objc),object position z(objc)
    set camera to object orientation objc
    set light to object position lightc, objc
    set light to object orientation lightc, objc
endfunction

function make_a_new_level()
    
    MG_clear_level()
    MG_init()
    randomize timer()
    MG_generate(rnd(100000))
    MG_create_level("","","")
    sc_setupcomplexobject MG_level_obj, 1, 2
    position object objc,MG_center_x_in(0),objcsize,MG_center_y_in(0)
endfunction



` ====================
` The types (structures)
type _VERT
    x as float
    y as float
endtype

type _EDGE
    v1      as integer
    v2      as integer
endtype

type _FACE
    v1      as integer
    v2      as integer
    v3      as integer
endtype

` ====================
` Initialise all the globals used by the generation algorithm
function MG_init()
    global  dim _VERTS()    as _VERT    ` main verts list
    global  dim _OUT()      as _EDGE    ` outer polygon edges
    global  dim _IN()       as _EDGE    ` inner edges
    global  dim _FACES()    as _FACE    ` floor faces
    
    global  dim _OBJ()      as integer  ` object ID's list
    global  dim _IMG()      as integer  ` texture list ID's
    
    global  MG_minx         as float    ` maps extents
    global  MG_miny         as float
    global  MG_maxx         as float
    global  MG_maxy         as float
    
    global  MG_rnd_mod      as integer  ` map random modulus values
    global  MG_rnd_add      as integer
    global  MG_rnd_div      as float
    
    global  MG_edge_length  as float    ` edges default length
    global  MG_edge_angle   as float
    
    global  MG_max_faces    as integer
    
    MG_edge_length  = 100.0
    MG_edge_angle   = 45
    
    MG_rnd_mod      = 50
    MG_rnd_add      = 100
    MG_rnd_div      = 100
    
    MG_max_faces    = 750
    
    ` Map extents globals
    global  MG_map_xmin     as float
    global  MG_map_ymin     as float
    global  MG_map_xmax     as float
    global  MG_map_ymax     as float
    
    ` main level object
    global  MG_level_obj    as integer
endfunction



` ====================
` returns 1 if line x1,y1,x2,y2 intersects x3,y3,x4,y4
` THE MOST IMPORTANT PIECE OF THIS COMPLETE ALGORITHM
function MG_intersect(x1#,y1#,x2#,y2#,x3#,y3#,x4#,y4#)
    d# = ( x1# - x2# ) * ( y3# - y4# ) - ( y1# - y2# ) * ( x3# - x4# )
    if d#=0 then exitfunction 0
    ` Get the x and y
    pre# = x1# * y2# - y1# * x2#
    post#= x3# * y4# - y3# * x4#
    x#=( pre# * (x3# - x4#) - (x1# - x2#) * post# ) / d#
    y#=( pre# * (y3# - y4#) - (y1# - y2#) * post# ) / d#
    ` Check if x and y are within both lines
    if ( x# < min(x1#, x2#) or x# > max(x1#, x2#) or x# < min(x3#, x4#) or x# > max(x3#, x4#) ) then exitfunction 0
    if ( y# < min(y1#, y2#) or y# > max(y1#, y2#) or y# < min(y3#, y4#) or y# > max(y3#, y4#) ) then exitfunction 0
endfunction 1

` ====================
` add a new vertex
function MG_add_vert(x#,y#)
    array insert at bottom _VERTS()
    _VERTS().x = x#
    _VERTS().y = y#
endfunction

` ====================
` add an outer edge
function MG_add_out(v1,v2)
    array insert at bottom _OUT()
    _OUT().v1 = v1
    _OUT().v2 = v2
endfunction

` ====================
` add an inner edge
function MG_add_in(v1,v2)
    array insert at bottom _IN()
    _IN().v1 = v1
    _IN().v2 = v2
endfunction

` ====================
` add face to the _FACES() array
function MG_add_face(v1,v2,v3)
    array insert at bottom _FACES()
    _FACES().v1 = v1
    _FACES().v2 = v2
    _FACES().v3 = v3
endfunction

` ====================
` Move outer edge to the inner edge list
function MG_move_edge(edge)
    array insert at bottom _IN()
    _IN().v1 = _OUT(edge).v1
    _IN().v2 = _OUT(edge).v2
    array delete element _OUT(), edge
endfunction

` ====================
` hard code the first 2 triangles
function MG_make_first_poly()
    ` first triangles verts
    MG_add_vert(0,0)
    MG_add_vert(MG_edge_length,0)
    MG_add_vert(0,MG_edge_length)
    ` store its edges
    MG_add_out(0,1)
    MG_add_in(1,2)  ` hide in the inner list
    MG_add_out(2,0)
    ` store as a face
    MG_add_face(0,1,2)
    ` add another vertex for 2nd triangle
    MG_add_vert(MG_edge_length,MG_edge_length)
    ` add the new edges to outer list
    MG_add_out(1,3)
    MG_add_out(3,2)
    ` add the new face
    MG_add_face(1,3,2)
endfunction

` ====================
` The main generation algorithm
function MG_generate(seed)
    ` get this bit out of the way
    randomize seed
    ` create the first polygon (2 triangles)
    MG_make_first_poly()
    ` init current face count
    face = 2
    
    while face < MG_max_faces
        outsize = array count( _OUT() )
        if outsize < 10
            edge = outsize - rnd( 1 )
        else
            edge = outsize - ( ( rnd( outsize ) * 12.0 ) / 100.0 )
        endif
        v1 = _OUT(edge).v1
        v3 = _OUT(edge).v2
        angle# = atanfull(_VERTS(v3).y - _VERTS(v1).y, _VERTS(v3).x - _VERTS(v1).x)
        angle# = wrapvalue(angle# - MG_edge_angle)
        edgelen# = MG_edge_length * ( rnd(MG_rnd_mod) + MG_rnd_add ) / MG_rnd_div
        `edgelen#=MG_edge_length
        x# = _VERTS(v1).x + ( cos(angle#) * edgelen# )
        y# = _VERTS(v1).y + ( sin(angle#) * edgelen# )
        if MG_face_in_poly(edge,x#,y#) = 0
            inc face
            MG_add_vert(x#,y#)
            MG_move_edge(edge)
            v2 = array count( _VERTS() )
            MG_add_out(v1,v2)
            MG_add_out(v2,v3)
            MG_add_face(v1,v2,v3)
        `    trace_write("Face count = "+str$(face))
        `    trace_write("-> face verts - "+str$(v1)+","+str$(v2)+","+str$(v3)+" - "+str$(x#)+","+str$(y#)+" - Edge: "+str$(edge))
        `else
        `    trace_write("Skipped")
        endif
    endwhile
    MG_get_map_extents()
    `trace_write("Totals: (Verts-"+str$(array count(_VERTS()))+"), (Faces-"+str$(array count(_FACES()))+")")
endfunction

` ====================
` Test if faces crosses inside the current main polygon
function MG_face_in_poly(edge,x#,y#)
    ostart  = _OUT(edge).v1
    oend    = _OUT(edge).v2
    if MG_test_outer(x#,y#,ostart) = 0
        if MG_test_outer(x#,y#,oend) = 0
            if MG_test_inner(x#,y#,ostart) = 0
                if MG_test_inner(x#,y#,oend) = 0
                    exitfunction 0
                endif
            endif
        endif
    endif
endfunction 1

` ====================
` test outer intersect
function MG_test_outer(x#,y#,v)
    curr_edge   = array count( _OUT() )
    startx#     = _VERTS(v).x
    starty#     = _VERTS(v).y
    flag        = 0
    while curr_edge >= 0 and flag = 0
        edge_start  = _OUT(curr_edge).v1
        edge_end    = _OUT(curr_edge).v2
        if v = edge_end or v = edge_start
            angle# = atanfull(y#-starty#, x#-startx#)
            linex1# = startx# + cos(angle#) * 1.0
            liney1# = starty# + sin(angle#) * 1.0
        else
            linex1# = startx#
            liney1# = starty#
        endif
        edge_x1# = _VERTS(edge_start).x
        edge_y1# = _VERTS(edge_start).y
        edge_x2# = _VERTS(edge_end).x
        edge_y2# = _VERTS(edge_end).y
        flag = MG_intersect(linex1#,liney1#,x#,y#,edge_x1#,edge_y1#,edge_x2#,edge_y2#)
        dec curr_edge
    endwhile
endfunction flag

` ====================
` test inner intersect
function MG_test_inner(x#,y#,v)
    curr_edge   = array count( _IN() )
    startx#     = _VERTS(v).x
    starty#     = _VERTS(v).y
    flag        = 0
    while curr_edge >= 0 and flag = 0
        edge_start  = _IN(curr_edge).v1
        edge_end    = _IN(curr_edge).v2
        if v = edge_end or v = edge_start
            angle# = atanfull(y#-starty#, x#-startx#)
            linex1# = startx# + cos(angle#) * 1.0
            liney1# = starty# + sin(angle#) * 1.0
        else
            linex1# = startx#
            liney1# = starty#
        endif
        edge_x1# = _VERTS(edge_start).x
        edge_y1# = _VERTS(edge_start).y
        edge_x2# = _VERTS(edge_end).x
        edge_y2# = _VERTS(edge_end).y
        flag = MG_intersect(linex1#,liney1#,x#,y#,edge_x1#,edge_y1#,edge_x2#,edge_y2#)
        dec curr_edge
    endwhile
endfunction flag

` ====================
` OUTER EDGE FUNCTIONS
function MG_center_x_out(edge)
    x# = ( _VERTS(_OUT(edge).v1).x + _VERTS(_OUT(edge).v2).x ) / 2.0
endfunction x#

function MG_center_y_out(edge)
    y# = ( _VERTS(_OUT(edge).v1).y + _VERTS(_OUT(edge).v2).y ) / 2.0
endfunction y#

function MG_edge_angle_out(edge)
    s = _OUT(edge).v1 : e = _OUT(edge).v2
    a# = atanfull(_VERTS(e).y - _VERTS(s).y, _VERTS(e).x - _VERTS(s).x)
endfunction a#

` ====================
` INNER EDGE FUNCTIONS
function MG_center_x_in(edge)
    x# = ( _VERTS(_IN(edge).v1).x + _VERTS(_IN(edge).v2).x ) / 2.0
endfunction x#

function MG_center_y_in(edge)
    y# = ( _VERTS(_IN(edge).v1).y + _VERTS(_IN(edge).v2).y ) / 2.0
endfunction y#

function MG_edge_angle_in(edge)
    s = _IN(edge).v1 : e = _IN(edge).v2
    a# = atanfull(_VERTS(e).y - _VERTS(s).y, _VERTS(e).x - _VERTS(s).x)
endfunction a#

` ====================
` calc the minimum x and y values from all the vertices
function MG_get_map_extents()
    MG_map_xmin = 0 : MG_map_ymin = 0
    MG_map_xmax = 0 : MG_map_ymax = 0
    
    vsize = array count( _VERTS() )
    
    while vsize >= 0
        currx# = _VERTS( vsize ).x : curry# = _VERTS( vsize ).y
        if MG_map_xmin > currx# then MG_map_xmin = currx#
        if MG_map_xmax < currx# then MG_map_xmax = currx#
        if MG_map_ymin > curry# then MG_map_ymin = curry#
        if MG_map_ymax < curry# then MG_map_ymax = curry#
        dec vsize
    endwhile
    `trace_write("Map extents: Min-"+str$(MG_map_xmin)+","+str$(MG_map_ymin)+" - Max-"+str$(MG_map_xmax)+","+str$(MG_map_ymax))
endfunction

` ====================
` Create the actual 3d object (it's ID is then put into MG_level_obj)
` if no texture files are passed then the program will generate one
function MG_create_level(t_floor$,t_wall$,t_roof$)
    MG_create_floor()
    
    obj = MG_create_roof() : mesh = find free mesh()
    make mesh from object mesh, obj : add limb MG_level_obj,1,mesh
    delete object obj : delete mesh mesh
    
    obj = MG_create_walls()
    make mesh from object mesh, obj : add limb MG_level_obj,2,mesh
    delete object obj : delete mesh mesh
    
    set object normals MG_level_obj
    calculate object bounds MG_level_obj
    
    if t_floor$=""
        img = MG_make_random_texture("F")
    else
        img = MG_load_texture(t_floor$)
    endif
    texture limb MG_level_obj, 0, img
    
    if t_wall$=""
        img = MG_make_random_texture("W")
    else
        img = MG_load_texture(t_wall$)
    endif
    texture limb MG_level_obj, 2, img
    
    if t_roof$=""
        img = MG_make_random_texture("R")
    else
        img = MG_load_texture(t_roof$)
    endif
    texture limb MG_level_obj, 1, img
    
    ` init collision (group 1)
    sc_setupcomplexobject MG_level_obj,1,2
    
    ` Decorate the floor of the level
    MG_decorate_floor()
endfunction

function MG_create_floor()
    MG_level_obj = find free object()
    vsize = array count( _VERTS() )
    fsize = array count( _FACES() )
    
    `trace_write("vsize="+str$(vsize)+" ,fsize="+str$(fsize))
    
    make object new MG_level_obj, vsize + 1, ( fsize + 1 ) * 3
    
    lock vertexdata for limb MG_level_obj, 0    ` open up object for editing
    
    for a = 0 to vsize
        x# = _VERTS(a).x : y# = _VERTS(a).y
        set vertexdata position a, x#, 0.0, y#
        ` I couldn't get the fmod() function working correctly so I've used
        ` the values from the maps extents to alter it to work properly
        u# = fmod( (x#+abs(MG_map_xmin)) / MG_edge_length, MG_edge_length)
        v# = fmod( (y#+abs(MG_map_ymin)) / MG_edge_length, MG_edge_length)
        set vertexdata UV a, u#, v#             ` vertex UV coorinates
    next
    
    for a = 0 to fsize
        face = a * 3
        set indexdata face    , _FACES(a).v1    ` set correct face orientation
        set indexdata face + 1, _FACES(a).v3
        set indexdata face + 2, _FACES(a).v2
    next
    
    unlock vertexdata                           ` now close the object
    
    set object MG_level_obj,1,1,1
endfunction

function MG_create_roof()
    obj = find free object()
    vsize = array count( _VERTS() )
    fsize = array count( _FACES() )
    
    make object new obj, vsize + 1, ( fsize + 1 ) * 3
    
    lock vertexdata for limb obj, 0
    
    for a = 0 to vsize
        x# = _VERTS(a).x : y# = _VERTS(a).y
        set vertexdata position a, x#, MG_edge_length, y#
        u# = fmod( (x#+abs(MG_map_xmin)) / MG_edge_length, MG_edge_length)
        v# = fmod( (y#+abs(MG_map_ymin)) / MG_edge_length, MG_edge_length)
        set vertexdata UV a, u#, v#
    next
    
    for a = 0 to fsize
        face = a * 3
        set indexdata face    , _FACES(a).v1
        set indexdata face + 1, _FACES(a).v2
        set indexdata face + 2, _FACES(a).v3
    next
    
    unlock vertexdata
    
    set object obj,1,1,1
endfunction obj

function MG_create_walls()
    obj = find free object()
    esize = array count( _OUT() )
    
    ` sort the outer edges in order
    dim walls() as _EDGE
    
    array insert at bottom walls()
    walls().v1 = _OUT(0).v1
    walls().v2 = _OUT(0).v2
    look = _OUT(0).v2
    
    while array count(walls()) < esize
        curr = 1
        while ( _OUT(curr).v1 <> look )
            inc curr
        endwhile
        vfound = _OUT(curr).v2
        array insert at bottom walls()
        walls().v1 = look : walls().v2 = vfound
        look = vfound
    endwhile
    
    ` now create the walls with correct UV's
    vert2 = array count( _VERTS() )
    
    make object new obj, (vert2+1)*2, (esize+1)*6
    lock vertexdata for limb obj, 0
    
    ` store vertex data (no UV being set just yet)
    for a = 0 to vert2
        x# = _VERTS(a).x : y# = _VERTS(a).y
        set vertexdata position a, x#,0.0,y#
        set vertexdata position a+vert2+1, x#,MG_edge_length,y#
    next
    
    ` set first vertex UV
    set vertexdata UV walls(0).v1, 0.0, 0.0
    set vertexdata UV walls(0).v1+vert2+1, 0.0, 1.0
    
    ` this next var will help wrap UV properly
    currUV# = 0
    
    start = walls(0).v1
    x1# = _VERTS(start).x
    y1# = _VERTS(start).y
    
    ` now loop through creating 2 triangle for each face
    ` and calculate UV based on the edge length
    for a = 0 to vert2
        vend = walls(a).v2
        x2# = _VERTS(vend).x
        y2# = _VERTS(vend).y
        length# = abs( sqrt((x2#-x1#)*(x2#-x1#) + (y2#-y1#)*(y2#-y1#)) )
        currUV# = currUV# + (length# / MG_edge_length)
        
        `trace_write("Edge no, Length = "+str$(a)+","+str$(length# / MG_edge_length))
        
        set vertexdata UV vend, currUV#, 0.0
        set vertexdata UV vend+vert2+1, currUV#, 1.0
        
        pos = a * 6
        set indexdata pos, start
        set indexdata pos+1, vend + vert2 + 1
        set indexdata pos+2, start + vert2 + 1
        
        set indexdata pos+3, start
        set indexdata pos+4, vend
        set indexdata pos+5, vend + vert2 + 1
        
        ` speeds up the loop a bit
        x1# = x2# : y1# = y2# : start = vend
    next
    
    unlock vertexdata
    
    undim walls()   ` free the temp memory used
endfunction obj

` ====================
` generates a random texture and returns it's image ID
function MG_make_random_texture(s$)
    bw=512 : bh=512
    dim cols(3)
    for a=0 to 3
        cols(a) = rgb( rnd(3)*64, rnd(3)*64, rnd(3)*64 )
    next
    bm = find free bitmap()
    create bitmap bm, bw, bh
    lock pixels
    for y=0 to bh-1
        for x=0 to bw-1
            dot x,y,cols(rnd(3))
        next
    next
    unlock pixels
    ink rnd(3),rnd(3)
    for x = 0 to bw-1 step text width(s$)*2
        for y = 0 to bh-1 step text height(s$)*2
            text x,y,s$
        next
    next
    for x = 0 to bw-1
        ink cols(rnd(3)),cols(rnd(3))
        if rnd(1)
            line rnd(bw-1),rnd(bh-1),rnd(bw-1),rnd(bh-1)
        else
            circle rnd(bw-1),rnd(bh-1),rnd(bw/4)
        endif
    next
    img = find free image()
    get image img, 0,0,bw-1,bh-1
    delete bitmap bm
    undim cols()
    array insert at bottom _IMG()
    _IMG() = img
endfunction img

` ====================
` load a texture and add to array
function MG_load_texture(file$)
    img = find free image()
    load image file$, img
    array insert at bottom _IMG()
    _IMG() = img
endfunction img

` ====================
` free up all the resources used by the level
function MG_clear_level()
    ` main level object
    sc_removeobject MG_level_obj
    delete object MG_level_obj
    
    ` textures
    for a=0 to array count( _IMG() )
        delete image _IMG(a)
    next
    
    ` main arrays
    empty array _VERTS()
    empty array _OUT()
    empty array _IN()
    empty array _FACES()
    
    ` objects
    for a=0 to array count( _OBJ() )
        if sc_collisionstatus( _OBJ(a) )
            sc_removeobject _OBJ(a)
        endif
        delete object _OBJ(a)
    next
    
    ` nothing else yet
endfunction

` let's make some floor obstacles
function MG_decorate_floor()
    img1 = MG_make_random_texture(">--<")
    img2 = MG_make_random_texture("#X#X#")
    insize = array count( _IN() )
    chance = rnd(80)+20
    for a=3 to insize
        if rnd(100)>chance
            x# = MG_center_x_in(a)
            y# = MG_center_y_in(a)
            a# = MG_edge_angle_in(a)
            sel = rnd(1)
            select sel
                case 0:
                    obj = find free object()
                    make object box obj, 70, 20, 15
                    yrotate object obj, a#
                    position object obj, x#, 10, y#
                    texture object obj, img1
                    sc_setupobject obj, 1, 2
                    array insert at bottom _OBJ()
                    _OBJ() = obj
                    endcase
                case 1:
                    obj = find free object()
                    make object sphere obj, 20
                    yrotate object obj, a#
                    position object obj, x#, 10, y#
                    texture object obj, img2
                    sc_setupobject obj, 1, 1
                    array insert at bottom _OBJ()
                    _OBJ() = obj
                    endcase
            endselect
        endif
    next
endfunction