Sorry your browser is not supported!

You are using an outdated browser that does not support modern web technologies, in order to use this site please update to a new browser.

Browsers supported include Chrome, FireFox, Safari, Opera, Internet Explorer 10+ or Microsoft Edge.

DarkBASIC Discussion / maths collision demo

Author
Message
29 games
18
Years of Service
User Offline
Joined: 23rd Nov 2005
Location: not entirely sure
Posted: 25th Mar 2010 20:40
I've recently been working on some maths collision code and have put together this demo to show you what I've come up with.

[/URL]

It's an FPS style demo, where the map is created entirely in DBC and then uses maths for sliding collision of the camera against the walls.

Rather than using the native DBC primatives for the walls, they're created from a memblock and specify the start and end point of the wall, which makes it easier to get them to join up properly





The code could probably stand a bit of tightening up, so comment would be welcome.

I've also included a pdf down load that shows the method and maths used. It's six pages but most of it's diamgrams.

[img]null[/img][img]null[/img]

Attachments

Login to view attachments
Libervurto
17
Years of Service
User Offline
Joined: 30th Jun 2006
Location: On Toast
Posted: 25th Mar 2010 21:34
Nice work!
It feels really solid and real, the map is nice too, I also like the purple.

"With games, we create these elaborate worlds in our minds, and the computer is there to do the bookkeeping." - Will Wright
29 games
18
Years of Service
User Offline
Joined: 23rd Nov 2005
Location: not entirely sure
Posted: 25th Mar 2010 22:33
I like the purple too but I'd probably use a simple texture to give it a bit more interest.

The funny thing about designing the map was that, even though I could have the walls at any angles, 90 and 45 degrees just looked right. I mean, how many rooms have you been in lately that don't have any right angles in? If you stick to 90 and 45 degrees, the maths can be boiled down to something a lot more simple. I had to force myself to use different angle, hence the "entrance" coridoor.
Ashingda 27
16
Years of Service
User Offline
Joined: 15th Feb 2008
Location:
Posted: 25th Mar 2010 22:42
Cool, custom collision for 3d eh. Only 1 thing are the walls suppose to disappear now and then?
Latch
17
Years of Service
User Offline
Joined: 23rd Jul 2006
Location:
Posted: 26th Mar 2010 01:07
Nice! Very smooth.

For the two sided plane, you can do a couple of different things:

1. use SET OBJECT obj,1,1,0 to turn culling off for the particular object.

2. when building the plane in the memblock, use 4 triangles instead of 2 to draw both sides. You can use the same vertices but reverse the index order for the opposite side of the plane. It will double your faces but it would still be less than using boxes or cubes.

Enjoy your day.
Libervurto
17
Years of Service
User Offline
Joined: 30th Jun 2006
Location: On Toast
Posted: 26th Mar 2010 05:19
Quote: "are the walls suppose to disappear now and then?"

I don't get walls disappearing. When does it happen?

"With games, we create these elaborate worlds in our minds, and the computer is there to do the bookkeeping." - Will Wright
29 games
18
Years of Service
User Offline
Joined: 23rd Nov 2005
Location: not entirely sure
Posted: 26th Mar 2010 22:49
I don't get wall disappearing either but I think Ashingda 27 might have edited to the map and found the walls are only visible from one side.

As Latch said, the plains can be made double sided but I sometimes find this cause grahical problems, a sort of shimmering distortion where two planes meet. I suspect there is a technical name for this but I don't know what it is This doesn't happen when using single sided plains.

If you decide to use waffer thin walls then you'll need to modify the collision code a bit.



The diagram on the left shows the area in which the camera will "collide" with the wall in the demo I posted. If walls are joined together to form an enclosed area then the point A of one line is in the same position as point B for another line. In this instance, checking collision a point B is unnecessary.

Rub the demo but only draw a single wall. When you move the camera at one end of the wall the collision will be smooth and at the other end the collision will be abrupt.

If you want smooth collision at both ends, an extra check has to be made so the COLLISION_WITH_WALL sub routine needs to be changed to this.



Effectively the maths now gives a collision area as shown in the diagram on the right.
Ashingda 27
16
Years of Service
User Offline
Joined: 15th Feb 2008
Location:
Posted: 26th Mar 2010 23:00
Quote: "I don't get walls disappearing. When does it happen?"

Well it's like I said it happens now and then, it's not consistent, very random.
29 games
18
Years of Service
User Offline
Joined: 23rd Nov 2005
Location: not entirely sure
Posted: 26th Mar 2010 23:47
In what way do the walls disapear? Do they flicker on and off or do they sort of vanish and reappear when you move the camera. Is it something you can post of screen grab of?
Ashingda 27
16
Years of Service
User Offline
Joined: 15th Feb 2008
Location:
Posted: 27th Mar 2010 01:16
Quote: "vanish and reappear when you move the camera"

Yup that's the one, it may just be for me.
29 games
18
Years of Service
User Offline
Joined: 23rd Nov 2005
Location: not entirely sure
Posted: 29th Mar 2010 14:37
I can't replicate the vanishing wall issue so I'm guessing it's one of those unfathomable problems that computers have.

There are a couple of things I could do differently. I could try making the plains double sided but what I might try next time is to make the map into a single model.
Latch
17
Years of Service
User Offline
Joined: 23rd Jul 2006
Location:
Posted: 29th Mar 2010 17:32
Or turn off culling.

Enjoy your day.
29 games
18
Years of Service
User Offline
Joined: 23rd Nov 2005
Location: not entirely sure
Posted: 29th Mar 2010 23:47
The plains created in the function CREATE_WALL are turned into static objects so the SET OBJECT obj,1,1,0 doesn't produce a 2 sided plain.

Using SET OBJECT ob,1,1,0 does give me a double sided plain (when it's an object) but when the plain is turned into a static object the plain goes back to being single sided. I also tried using the DISABLE STATIC OCCLUSION command but this doesn't give a two sided plain (I may not be understanding what this command does but I thought I'd give it a go).

The walls can all be left as individual objects but I'm reluctant to do this as it could be a pain for more complex maps.

Also, if I do leave the walls as double sided plains then colour from the back face of hidden walls is visble at the edge of where walls meet and looks a bit scruffy.

I'm going to leave the demo as it is for the time being, as I'm currently working on some other things (creating objects from memblocks and more maths collision) but I'll come back to it at some point.

Thanks
Latch
17
Years of Service
User Offline
Joined: 23rd Jul 2006
Location:
Posted: 2nd Apr 2010 03:10
@29 Games
What makes terrain height finding super fast with objects (when not using matrices in DBC) when using math, is that if the terrain is uniform in the x and z directions (it doesn't have to be square, each tile ideally has to have the same x width and the same z depth), the grid square you are over can be calculated on the fly without having to loop through any triangles. By knowing the faces you are over you can quickly get the verts and calculate the height.

Couldn't you do something similar since you are storing your wall information in an array? If you index your walls based on their center, you could eliminate groups of searches by checking if the camera position > or < than a certain index.

For example, let's say that you add walls starting from 0,0,0 and keep adding walls until the last one is somewhere like 1000,0,1000. You basically are building from -x to +x and from -z to +z. Each wall or group of walls that is below a certain z or x value, say x=500 and z=500, are assigned an index number. In the main program, if the player or camera position is within a certain index that represents a certain position or limit on positions, the only walls that are checked for collision are those that meet the index reequirements. In this example of using 500 as a cutoff, that could quarter you search time.

Looking at your code, it seems that you loop through every wall reagrdless of whether there is collision or not. Can you exit the loop as soon as you determine collision?

Enjoy your day.
29 games
18
Years of Service
User Offline
Joined: 23rd Nov 2005
Location: not entirely sure
Posted: 4th Apr 2010 00:01
For the demo, I decided that I wasn't going to spend time on optimising the code for speed, I just wanted to concentrate on implementing the maths.

Latch, you're absolutely right when you say the program goes through every single wall, regardless, so exiting the loop once a collision has been detected make sense. I also think using an indexing system as you suggest is a good idea.

This will probably be something I look into when I come to write a game using the code.
29 games
18
Years of Service
User Offline
Joined: 23rd Nov 2005
Location: not entirely sure
Posted: 23rd Jun 2010 21:38 Edited at: 23rd Jun 2010 21:43
I've been doing a bit more work with maths collision. It addresses some of the comments Latch made about reducing the number of collision calculations.




You can jump onto things, crouch and move under things, and walk up and down the stairs.



There are a couple of minor glitches, the main one being that it's possible to get stuck at the bottom of the stairs if you slide agianst the side of them (you can jump out of it).

I was going to add a few more things to this post but for some reason it wouldn't let me post the whole lot in one go. If this works I'll do another post.
29 games
18
Years of Service
User Offline
Joined: 23rd Nov 2005
Location: not entirely sure
Posted: 23rd Jun 2010 21:47
My god, posting that was a nightmare! I have no idea what was going on there.

Anyway, I will appologize for the double post but there are a couple of other things that might be of interest.

The first, is the way the number of collision calculations were reduced.

Looking at the different options, the idea I settled on was treating the map like a database. So the map is split into a grid and each square of the grid contains an ident of any map objects that are either partly or wholly in the square. Collision detection is then only performed on those obstacles that are in the same square as the moving object.

A simple 2D demo of this is shown below:



This allows map objects to be placed anywhere, with need to divede the map into quaters, say, or have only a single object per square of the grid - although a maximum limit needs to be set. The down side is putting together the database but this could be created as part of a level editor. It can, however, be made to work with any type of collision detection.

Incedentally, on my last demo I tried the idea of exiting the collision detection loop once a collision with a wall had taken place but found that I could walk into a corner, slide against one wall and walk through the adjoining wall.

The next code snippet I have is a point in triangle function which I have expanded into a point in four sided shape demo:




The basic theory for how this works can be found here:

http://www.blackpawn.com/texts/pointinpoly/default.html

As always, comments are welcome.
Latch
17
Years of Service
User Offline
Joined: 23rd Jul 2006
Location:
Posted: 23rd Jul 2010 06:10
@29 games

This is some good stuff. Would it be possible for you to adapt this to loading in a 3d object, converting it to a memblock, and testing collision on that object based on the faces and points read from the memblock?

Enjoy your day.
mieketsai
13
Years of Service
User Offline
Joined: 23rd Jul 2010
Location:
Posted: 23rd Jul 2010 11:20
well done!
29 games
18
Years of Service
User Offline
Joined: 23rd Nov 2005
Location: not entirely sure
Posted: 23rd Aug 2010 19:14
Thanks for the comments.

I've been having a think about how to use an object's vertex and face data for collision purposes. The maths for sliding collision seemed a bit fierce at first glance so I decided to have a look at something a bit more simple (but even this started to push the limits of what I would consider to be fun).

The demo below shows a method for determining if a cross hair is on an object, using "line through polygon" maths.





This will work with any object but I tried it with a model that had 1500 faces (I don't know if this is big or not) and it slowed down to 20 fps.

However, I suspect that doing full on sliding collision now wouldn't be much of a leap.

I think in order to use an object for the map and then use its vertex and face data you have to either:

simplify the data for the maths collision so you're not dealing with 3D polgons (ie. determine if walls are verical and rectangular and that all floors and ceilings are horizontal, for instance)

or

reduce the number of polygons that are considered in each loop (ie, ignore polygons that are far away).

Preferably both.

By creating the map in the way I have in the two demos the data is simplified so the maths is less intense. Simple things like having all the walls vertical and all the floors and ceilings horizontal have a huge effect on keeping the maths simple.

I can see the appeal of simply loading in an object for a map (for those who like 3D modelling) but I'm not entirely sure how easy it would be in practice. I guess it must be possible.

I think it would be just as easy to create a level editor in DBC to suit the way I'm creating maps and doing the maths collision.

Login to post a reply

Server time is: 2024-03-28 19:30:34
Your offset time is: 2024-03-28 19:30:34