I need to calculate and display the convex hull of 2D polygons in the editor for that 3d thing, so I implemented a quick (as in "divide and conquer") algorithm for it. I remember writing a quick algorithm for the convex hull of a set of random points in 3D at the university, which is a bit trickier.
If you ever need to calculate the convex hull for a polygon or a bunch of points, you can use this
Code:
' Convex hull test
' ----------------
set window "test", 640, 480
set redraw off
do
set color 0, 0, 0
cls
' Create 100 random points.
points = []
for i = 1 to 100
a = rnd()*2*PI
r = rnd(200)
points[sizeof(points)] = 320 + cos(a)*r
points[sizeof(points)] = 240 + sin(a)*r
next
' Draw points.
set color 255, 255, 255
pcount = sizeof(points)/2
for i = 0 to pcount - 1
draw pixel points[i*2], points[i*2 + 1]
next
' Display and wait one second.
redraw
wait 1000
' Calculate convex hull and display it.
hull = ConvexHull(points)
draw poly hull
set caret width(primary)/2, 4
center "Press space bar to continue ..."
redraw
while not keydown(KEY_SPACE, true) fwait 60
loop
' ConvexHull
' ----------
' Calculate the convex hull for a set of points in an array [x0, y0, x1, y1 ..], return as a polygon
' in the same format.
function ConvexHull(points)
pcount = sizeof(points)/2
xminIndex = 0; xmaxIndex = 0
for i = 1 to pcount - 1
x = points[i*2]
if x < points[xminIndex*2] xminIndex = i
if x > points[xmaxIndex*2] xmaxIndex = i
next
lpoints = []; rpoints = []
for i = 0 to pcount - 1
if i <> xminIndex and i <> xmaxIndex
cp = CrossProd(points[xminIndex*2], points[xminIndex*2 + 1],
points[xmaxIndex*2], points[xmaxIndex*2 + 1],
points[i*2], points[i*2 + 1])
if cp < 0
lpoints[sizeof(lpoints)] = points[i*2]
lpoints[sizeof(lpoints)] = points[i*2 + 1]
elseif cp > 0
rpoints[sizeof(rpoints)] = points[i*2]
rpoints[sizeof(rpoints)] = points[i*2 + 1]
endif
endif
next
hull = []
hull[sizeof(hull)] = points[xminIndex*2]
hull[sizeof(hull)] = points[xminIndex*2 + 1]
HullRec(hull, lpoints, points[xminIndex*2], points[xminIndex*2 + 1], points[xmaxIndex*2], points[xmaxIndex*2 + 1])
hull[sizeof(hull)] = points[xmaxIndex*2]
hull[sizeof(hull)] = points[xmaxIndex*2 + 1]
HullRec(hull, rpoints, points[xmaxIndex*2], points[xmaxIndex*2 + 1], points[xminIndex*2], points[xminIndex*2 + 1])
return hull
function HullRec(hull, points, x0, y0, x1, y1)
if not sizeof(points) return
pcount = sizeof(points)/2
maxd = 0; maxdIndex = -1
for i = 0 to pcount - 1
x = points[i*2]; y = points[i*2 + 1]
d = LinePointDist(x0, y0, x1, y1, x, y)
if d > maxd
maxd = d
maxdIndex = i
endif
next
npoints = []
for i = 0 to pcount - 1
if i <> maxdIndex
x = points[i*2]; y = points[i*2 + 1]
cp = CrossProd(x0, y0, points[maxdIndex*2], points[maxdIndex*2 + 1], x, y)
if cp < 0
npoints[sizeof(npoints)] = x
npoints[sizeof(npoints)] = y
endif
endif
next
if sizeof(npoints)
HullRec(hull, npoints, x0, y0, points[maxdIndex*2], points[maxdIndex*2 + 1])
endif
hull[sizeof(hull)] = points[maxdIndex*2]
hull[sizeof(hull)] = points[maxdIndex*2 + 1]
npoints = []
for i = 0 to pcount - 1
if i <> maxdIndex
x = points[i*2]; y = points[i*2 + 1]
cp = CrossProd(points[maxdIndex*2], points[maxdIndex*2 + 1], x1, y1, x, y)
if cp < 0
npoints[sizeof(npoints)] = x
npoints[sizeof(npoints)] = y
endif
endif
next
if sizeof(npoints)
HullRec(hull, npoints, points[maxdIndex*2], points[maxdIndex*2 + 1], x1, y1)
endif
endfunc
This is not meant to be a proper simulation (as you will see if you run it ), but just an experiment with the terrific circle-line functions that Marcus provided a while back. I've used the functions as they were originally written by Marcus, with one small alteration to the polygon function, where I have added a fifth argument to allow me to specify a point around which the polygon is rotated, rather than the center point of the polygon (I needed this for the 2 flippers).
There a few values that can be altered in the code to change the way that the ball reacts to certain lines - I've marked some of these as "arbitrary values", and I'm sure changing these will make for a smoother game, but I've decided to move on to a new project.
Control the flippers with the A and D keys, and launch the ball using the UP arrow.
Code:
' Experiment.
set window "PINBALL", 480, 640
set redraw off
#win32
visible score = 0
' List of lines that objects can collide with.
left_flipper = []
right_flipper = []
l_flipper = Polygon([0,0,10,-10,60,30,60,40], 140,580, true,[0,0])
r_flipper = Polygon([0,0,-10,-10,-60,30,-60,40], 300,580, true,[0,0])
'=============================================================================
'Note -added fifth argument to Polygon - 0 rotates around center point, or
'use a 2 part table to rotate around any point in the polygon - i.e. [32,34]
' to rotate around the fourth point in the polygon array here : -
'l_flipper = Polygon([0,0,10,0,32,24,32,34,22,34,0,10], 320, 240, true,[32,34])
'==============================================================================
l_flipper.AddTo(left_flipper)
left_flipper_timer = 0
left_ang = 0
'triangles sticking out of side - not bouncing
lines[sizeof(lines)] = Line(0,380,40,380)
lines[sizeof(lines)] = Line(0,310,40,380)
lines[sizeof(lines)] = Line(440,380,400,380)
lines[sizeof(lines)] = Line(400,380,440,310)
PushOut(obj, right_flipper)
if obj.pdy < 0
if r_flipper.Angle() <> 0
obj.dy = - 10
right_ang = angle_rad(r_flipper.trans[2][0],r_flipper.trans[2][1],r_flipper.trans[1][0],r_flipper.trans[1][1])
right_vecs = get_vecs(right_ang)
obj.dx = obj.dx + right_vecs[0] * 32'arbitrary figure
endif
endif
'==================================
PushOut(obj, bouncers)' make them bounce a little
if obj.pdx <> 0 or obj.pdy <> 0
obj.dx = obj.dx + obj.pdx*12'arbitrary figure
obj.dy = obj.dy + obj.pdy*12 'arbitrary figure
endif
PushOut(obj, lines)
'
if obj.y < 180 and obj.x > 240 and obj.dx < 0' help with initial lauch of ball
if obj.pdx <> 0 or obj.pdy <> 0
obj.dx = obj.dx + obj.pdx*4'arbitrary figure
endif
endif
if obj.y < 180 and obj.x < 240 ' help with initial lauch of ball
if obj.pdx <> 0 or obj.pdy <> 0
obj.dx = obj.dx + obj.pdx*0.3'arbitrary figure
obj.dy = obj.dy + obj.pdy*1
endif
endif
' obj.pdx and obj.pdy has now been set to the average "push direction" caused by all lines
' pushing the object around.
' Push direction y < 0 means the object is being pushed UP. In that case, set dy to 0.
if obj.pdy < 0
' If push direction y < -0.25, let the player jump.
if obj.pdy < -0.25 and keydown(KEY_UP, true) and obj.x >= 455
obj.dy = -14
endif
endif
' Apply gravity.
obj.dy = min(obj.dy + 0.1, 6)
' So ... stuff to dx.
obj.dx = obj.dx + obj.pdx*0.25 ' I have no idea
obj.dx = obj.dx*0.95
set color 0, 0, 0
cls
set color 255, 255, 255
DrawLines(lines)
DrawLines(circles)
DrawLines(bouncers)
DrawLines(left_flipper)
DrawLines(right_flipper)
obj.Draw()
set caret 20,10
set justification left
write "SCORE : " + score;wln
' set caret 460,10
' set justification right
' write "FPS = " + str(fps);wln
####### FPS calc ############################
endtime = clock()
frametime = frametime + endtime - starttime
if frametime > 1000 # 1 second
fps = framecount
framecount = 0
frametime = 0
if fps < min_fps then min_fps = fps
if fps > max_fps then max_fps = fps
endif
################################################
wend
function DrawLines(lines)
foreach ln in lines draw line ln[0], ln[1], ln[2], ln[3]
endfunc
function Object(x, y, r)
return [x: x, y: y, r: r, rsqr: r*r, pdx: 0, pdy: 0,
Draw: function(); draw ellipse .x, .y, .r, .r, false; endfunc]
endfunc
' Pushout
' -------
function PushOut(obj, lines)
tests = 4
obj.pdx = 0
obj.pdy = 0
for i = 1 to tests
col = false
foreach ln in lines
dp = max(0, min(ln[6], (obj.x - ln[0])*ln[4] + (obj.y - ln[1])*ln[5]))
px = ln[0] + dp*ln[4]; py = ln[1] + dp*ln[5]
dx = obj.x - px; dy = obj.y - py
d = dx*dx + dy*dy
if d < obj.rsqr
k = 1/sqr(d)
obj.x = px + dx*k*obj.r
obj.y = py + dy*k*obj.r
obj.pdx = obj.pdx + dx*k
obj.pdy = obj.pdy + dy*k
col = true
endif
next
if not col break
next
if obj.pdx or obj.pdy
k = 1/sqr(obj.pdx*obj.pdx + obj.pdy*obj.pdy)
obj.pdx = obj.pdx*k
obj.pdy = obj.pdy*k
endif
endfunc
' Polygon
' -------
' Return polygon at position x, y.
' Polygon
' -------
' Return polygon at position x, y.
'function Polygon(points, x, y, closed,rotation_point_x,rotation_point_y)
function Polygon(points, x, y, closed,rotation_point)
'========================================================================
'Note - added fifth argument to Polygon - 0 rotates around center point, or
'use a 2 part table to rotate around any point in the polygon - i.e. [32,34]
' to rotate around the fourth point in the polygon array here :-
'l_flipper = Polygon([0,0,10,0,32,24,32,34,22,34,0,10], 320, 240, true,[32,34])
'========================================================================
p = [trans: unset, org: [], x: x, y: y, a: 0, cx:0, cy: 0]
pcount = sizeof(points)/2
centerX = 0
centerY = 0
if closed n = pcount - 1
else n = pcount - 2
for i = 0 to n
j = (i + 1)%pcount
p.org[sizeof(p.org)] = Line(
points[i*2], points[i*2 + 1],
points[j*2], points[j*2 + 1])
next
for i = 0 to pcount - 1
if rotation_point = 0
p.cx = p.cx + points[i*2]; p.cy = p.cy + points[i*2 + 1]
else
p.cx = rotation_point[0] * pcount 'rotation_point_x
p.cy = rotation_point[1] * pcount ' rotation_point_y
endif
next
Building a level, walls; floors and ceilings, I can do... but I get a little confused with placing items... I can place item on the ceiling and floors ok. But the "indexes" for the items I am not all that familiar. Do the "item" indexes have to be the same as the image "indexes"?
Would there be a RC PDF squirreled away on some drive per chance?
This is just a walls, floor and ceiling layout of the first level modeled after the actual Wolf3D game... This is just a navigable concept level of 64x64 tiles... just to see how N7 copes performance wise...
I will probably use a different tileset for the complete game (assuming I can get that far... lol)... It would be a good idea not to step on Apogee's toes... lol
Of course, the usual constructive criticisms and suggestions, are always welcome....
Disclaimer
No person or entity associated with this game received payment or anything of value, or entered into any agreement,
in connection with the depiction of the ancient egyptian culture and with any game assets used in this game. \
No mummies were harmed in the making of this game. Any similarity to any person living or dead is coincidental
Stage
Stage 1. Sand Desert in s3d
First thing first, find a hieroglyph magic spell. Without the spell, you can't eliminate a mummy.
Cast the spell in a relative close distance. But, don't too close to the mummy.
control key : SPACE BAR, Mouse, S
Stage 2. Maze inside the Pyramid in wolf3d
The maze grid size is small, so you don't need a map.
The maze is auto-generated using random maze algorithm.
control key : LEFT, RIGHT, UP, DOWN, SPACE BAR
-. Find a key to hidden knowledge
-. Enjoy your egyptian treasures
-. Taste the magical amulet
-. Wear a super diamond
-. Search for the Pharaoh's Sceptre
Hints :
1. Turn on your best sound system. Experience the creepy atmosphere. Don't play this game after midnight.
2. Don't skip or press ESC too soon, just enjoy every scene.
Note :
This game uses new library of s3d. It's really injected new fresh energy into the classic horror theme with its contemporary and somewhat experimental approach to the 3D world. Thanks to Marcus for providing feedback especially on how to put a mummy and example on how to use heightmap using s3d library and thanks to Johnno for MazeGen
If memory serves correctly, at one time, you stated that Wolf3D did not have an editor... I have noticed that the command structure for Wolf3D is quite similar to that of N6's Raycaster. Is it at all possible that the RC editor may be modified for Wolf3D use? But, then again, what about using the Tilemap Editor? Even if it is to just create the a "map[]" file to be read by Wolf3D... Just a thought or two... (Ok... You can stop chuckling now... *sighh*)
I made a very crude "platformer" 'map' editor, using a language that shall not be named, but it is quite limited in what it can do... but, what it does do, is create a text file of the level map. I suppose, assuming I have the ability to do so, I could try to modify the output file to reflect the same structure "map = []" uses... Warning: This will be a "stretch" for me... I am not certain that I can properly convert the base program to N7... If I can, then I shall discuss the limitations in more detail... Please do not hold your breath whilst you wait.... lol
I just thought I'd post an example of the current state of that 3d thing I'm working on. It's just an executable where you walk around in a level created with the editor. No source code or editor included this first time. There are still no "sub sectors", so a single sector always have the same floor and wall height. Next time I promise you more advanced rooms and some decoration meshes.
Walk with WASD and look around with the mouse. There is a settings menu where you can change some graphical things and mouse sensitivity (the menu pops up as soon as you start, and you can bring it up again with the escape key).
Edit You will see that the walls "wiggle" when you walk along them at close range. That's an effect caused by lerping instead of doing fully perspective correct texture mapping. I may improve that the next time I update the S3D library. But that will have to wait until this engine is ready and I've made a game with it.
Do not ask about version one. Let's not go there... lol
Anyway... Here is version 2 using the new pixeli() command for collision detection.
You know how it works. Left and right arrow keys to move left and right. Up arrow to apply vertical thrust. Land on the green Pad. (Not too fast) Watch your fuel... there is no more until the very last level. Spoiler alert: Hold your breath for level nine.
ToDo:
Collision detection still flaky for level 10.
No background noise or music track.... open to suggestions.
Add "your" recommendations... (assuming "I" can do it. lol)
The mummy is everywhere when I am facing North, South, West etc ... lol .....
Is there a way to put the mummy somewhere in certain coordinate (x,y,z) ?
Code:
'==================================================
' THE MAZE II
' Part 1. Sand Desert
' Part 2. to be
' Part 3. to be
'
' Control :
' SPACE = move forward
' Mouse = see around
'
' Reference :
' - s3d.n7 library, ex6_heightmap.n7 by Marcus
'
' Sand texture https://images.app.goo.gl/QwsHZq7hZVdyNXB76
' Mummy1 https://images.app.goo.gl/uiosCKdMHraZPfoC7
' Title https://images.app.goo.gl/AGLmRC8g9vQDg21Q6
'==================================================
'----------------
' INITIALIZATION
'----------------
include "data_maze2/heightmap_library.n7"
include "s3d.n7"; S3D_SetView(primary, rad(90), 0.1, 5)
set window "Maze 2 - Part 1.Sand Desert",400,200,false,3
set mouse off
set redraw off
'color definition
gray = [128,128,128]
black = [0,0,0]
white = [255,255,255]
red = [255,0,0]
green = [0,255,0]
darkgreen = [0,128,0,120]
' Just simple draw image
set color white
draw image mummy[1].img, 20,20
'------------
' navigation
'------------
set color black
set caret 0,0; wln "Angle "+camYaw 'camYaw = 0 south, 90 east, 180 north, 270 west
wln "Position "+pos.x+","+pos.y+","+pos.z
set color darkgreen ; draw ellipse map.cx,map.cz,map.r,map.r,true
set color green
draw ellipse map.cx,map.cz,map.r,map.r
draw line map.cx,map.cz,map.cx+map.r*cos(rad(map.a)),map.cz+map.r*sin(rad(map.a))
set color red ; draw ellipse (map.x+int(pos.x)),(map.z+int(pos.z)),2,2,true
set color white ; draw ellipse (map.x+int(pos.x)),(map.z+int(pos.z)),2,2
set caret map.cx-18, map.z-13; wln "North"
set caret map.cx-18, map.z+map.h; wln "South"
set caret map.x-35, map.cz-5; wln "West"
set caret map.x+map.w+5, map.cz-5; wln "East"
I wrote a quick test for how collisions between moving objects (player and enemies) and the static walls should work in that 3d thing I'm working on. In the game/engine I will just check for collisions with walls close to the moving objects (a uniform grid will contain information about which walls passes through each cell). But maybe someone may still find this test useful for their own purposes:
Code:
set window "Collision", 640, 480
set redraw off
lines = []
randomize 11
for i = 1 to 8
ln = [rnd(640), rnd(480), rnd(640), rnd(480)]
dx = ln[2] - ln[0]; dy = ln[3] - ln[1]
ln[6] = sqr(dx*dx + dy*dy)
ln[4] = dx/ln[6]
ln[5] = dy/ln[6]
lines[sizeof(lines)] = ln
next
obj = Object(320, 240, 16)
while not keydown(KEY_ESCAPE, true)
'obj.x = mousex(); obj.y = mousey()
if keydown(KEY_LEFT) obj.x = obj.x - 4
if keydown(KEY_RIGHT) obj.x = obj.x + 4
if keydown(KEY_UP) obj.y = obj.y - 4
if keydown(KEY_DOWN) obj.y = obj.y + 4
PushOut(obj, lines)
set color 0, 0, 0
cls
set color 255, 255, 255
DrawLines(lines)
obj.Draw()
set caret width(primary)/2, 0
center "Use the arrow keys to move the circle around"
redraw
fwait 60
wend
function DrawLines(lines)
foreach ln in lines draw line ln[0], ln[1], ln[2], ln[3]
endfunc
function Object(x, y, r)
return [x: x, y: y, r: r, rsqr: r*r,
Draw: function(); draw ellipse .x, .y, .r, .r, false; endfunc]
endfunc
function PushOut(obj, lines)
' Let all lines push the object around a maximum of 10 times. This is not a recommended
' approach, just for testing.
tests = 10
for i = 1 to tests
col = false
foreach ln in lines
dp = max(0, min(ln[6], (obj.x - ln[0])*ln[4] + (obj.y - ln[1])*ln[5]))
px = ln[0] + dp*ln[4]; py = ln[1] + dp*ln[5]
dx = obj.x - px; dy = obj.y - py
d = dx*dx + dy*dy
if d < obj.rsqr
k = 1/sqr(d)
obj.x = px + dx*k*obj.r
obj.y = py + dy*k*obj.r
col = true
endif
next
if not col break
next
endfunc
This is pretty much how I did it in the GLOOM library for n6 too, if my memory is correct (source code since long gone).
![[Image: that_thing_editor.jpg]](https://naalaa.com/tmp/that_thing_editor.jpg)
![[Image: that_thing.jpg]](https://naalaa.com/tmp/that_thing.jpg)
