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 Professional Discussion / substitute for large arrays ( 10000 x 10000 etc )

Author
Message
Garion
18
Years of Service
User Offline
Joined: 7th Dec 2007
Location: Poland
Posted: 7th Feb 2010 19:06
Link
Hello.

I'm trying to make terrain collision, but I've got few thousands of units so sparky dll is too slow (about 3 fps...). I figured I can just precalculate the heights and store them, but I've got a 10000 x 10000 terrain (1 unit fits in a 1 tile). But of course it freezes. Is there a substitute?

(the mesh is just 100x100 poly but 100,100 array is not precise enough and I can't figure the algorytm to efficiently calculate points between those stored...)
Back to top
Profile PM Email
Mobiius
Valued Member
23
Years of Service
User Offline
Joined: 27th Feb 2003
Location: The Cold North
Posted: 8th Feb 2010 14:01
Link
A 100x100 poly terrain should run in sparkys fine?

And the interpolation code you could use is:

where V1# = lower Value, V2# = upper value and A# = distance between them. (In percent)

For example, if the player was between point 10, and point 11, V1# would be the height at point 10, V2# would be the height at point 11, and A# would be the distance between them.

The code would be something like this (Assuming were working on the X axis, Point10 is the XPosition of element 10, point11 is the XPosition of element11, Height10 is the height of Point10, Height11 is the height of Point11, playerPos is the X position of the player)...



My signature is NOT a moderator plaything! Stop changing it!
Back to top
Profile PM Email Website
Van B
Moderator
23
Years of Service
User Offline
Joined: 8th Oct 2002
Location: Sunnyvale
Posted: 8th Feb 2010 15:15
Link
Yeah, strange way to do this mate!

You can use what we call interpolation, like if you had a 100x100 heightmap, you would check these against the 2D X and Z location of the player with interpolation. Basically it's a fast and fairly easy ground height check - in some of my projects I've used hundreds per cycle with little concern for frame rate.

I'll post up the function if you let me know what your grid sizes are, and what array your heightmap is stored in.

This only solves the terrain ground height - you'd still need something for other objects, which is why sometimes it's better just to use real collision (or physics engines) instead of interpolation.


Health, Ammo, and bacon and eggs!
Back to top
Profile PM Email
Garion
18
Years of Service
User Offline
Joined: 7th Dec 2007
Location: Poland
Posted: 8th Feb 2010 20:21
Link
Mobiius
This interpolation function wouldn't work for 3D, only for 2D I think That's where the problems started in fact...

Van B
For other objects I just use arrays (like a 2D tile map)... so I only need to figure out the height of the ground:

I used a normal object for terrain and that's why I tried sparky's, but like I said, when I had 10 000 soldiers walking around, even simple ground height check became sloow.

I ran some tests and it seems that the build-in DBP terrain and it's GET TERRAIN GROUND HEIGHT is much, much faster (runs smoothly).

For now I moved from objects to advanced terrain. But I see that interpolation method on 2d heightmap would be pretty clever and probably even faster. I know how to calculate interpolation in X, and in Y, but I fail whenever I try to combine those two...


Thank you for replying
Back to top
Profile PM Email
Mobiius
Valued Member
23
Years of Service
User Offline
Joined: 27th Feb 2003
Location: The Cold North
Posted: 9th Feb 2010 08:00
Link
Quote: "This interpolation function wouldn't work for 3D"

Yes it would. You run that command once for the X axis, then once for the Z axis. Results are on the Y axis. Sounds like 3 dimensions to me.

My signature is NOT a moderator plaything! Stop changing it!
Back to top
Profile PM Email Website
Garion
18
Years of Service
User Offline
Joined: 7th Dec 2007
Location: Poland
Posted: 9th Feb 2010 19:31
Link
Yeah but it gives two different heights, and they're not 50%-50%... aren't they?
Back to top
Profile PM Email
Neuro Fuzzy
19
Years of Service
User Offline
Joined: 11th Jun 2007
Location:
Posted: 9th Feb 2010 22:07 Edited at: 9th Feb 2010 22:08
Link
you add their difference from the point smallest on the x and z axis.

[edit]
at school comp sci. will post more detailed when I get home. period ends in 1 minute


Back to top
Profile PM Email
Madscientist
16
Years of Service
User Offline
Joined: 23rd Aug 2009
Location: Between a rock and a hard place
Posted: 9th Feb 2010 22:55
Link
I have a 1024 poly terrain and it works fine with sparky's.

If it hasn't exploded yet, I haven't touched it.
Back to top
Profile PM
Alfa x
20
Years of Service
User Offline
Joined: 1st Jul 2006
Location: Colombia
Posted: 9th Feb 2010 22:57
Link
Garion, tey should give to you the same result.
Solve the equations.
Back to top
Profile PM Email
Neuro Fuzzy
19
Years of Service
User Offline
Joined: 11th Jun 2007
Location:
Posted: 10th Feb 2010 00:30
Link
where...

<x1,z1> is the position of the player
<x2,y2,z2> is the position of the vertex with the smallest z and x values
<x2,y3,z2+1> is the position of the vertex one in front of vert 2
<x2+1,y4,z2> is the position of the vertex one to the right of vert 2

n2=x1-x2
n1=z1-z2
y = (y3-y2)*n1+(y4-y2)*n2+y2

but where...
<x2,y3,z2+s> is the position of the vertex one in front of vert 2
<x2+s,y4,z2> is the position of the vertex one to the right of vert 2
then
n2=(x1-x2)/s
n1=(z1-z2)/s
y = (y3-y2)*n1+(y4-y2)*n2+y2

coming up with a demo program to verify it. I did something with this before (for a conic sections program), and I'm pretty sure the above is right, but still should check.


Back to top
Profile PM Email
Garion
18
Years of Service
User Offline
Joined: 7th Dec 2007
Location: Poland
Posted: 14th Apr 2010 19:03
Link
Quote: ""I have a 1024 poly terrain and it works fine with sparky's.""


By units I ment not size but actual alive units

I wonder how usual DBP terrain's GET GROUND HEIGHT works, it's incredibly fast

Neuro Fuzzy... I don't know if I get your calculations, so I did what I always do, I painted a picture for you

http://garion.pixa.us/images/18799695/%20wytlumacz
Back to top
Profile PM Email
Green Gandalf
VIP Member
21
Years of Service
User Offline
Joined: 3rd Jan 2005
Playing: Malevolence:Sword of Ahkranox, Skyrim, Civ6.
Posted: 14th Apr 2010 19:34
Link
Quote: "By units I ment not size but actual alive units "


What does "actual alive units" mean?

Quote: "I wonder how usual DBP terrain's GET GROUND HEIGHT works, it's incredibly fast"


I don't know how that works but it's simple enough to create your own function if you know how the terrain is constructed - which you do of course since you created it yourself.

Just create a function which looks up the right poly and its vertices then read the right values using the vertexdata commands - plus a bit of interpolation.
Back to top
Profile PM Email
Hawkblood
16
Years of Service
User Offline
Joined: 5th Dec 2009
Location:
Posted: 14th Apr 2010 20:53
Link
Ok. I think there are too many chiefs and not enough indians, so I'll be the next chief.... lol.

You have a 100x100 polly ground==> 10,000 pollys. The diminsions are 10000x10000==> each polly (grid) is 100x100 diminsional units in size. You want to move 10,000 soldiers on this terrain, so doing a collision check for each is going to slow you down to a crawl. Using an array of 10000,10000 makes your machine lock up?

Use the interpolation suggested earlier-- it will work.
Use memblocks instead of an array-- arrays use too much memory for each cell.

Linear interpolation is straight forward:
You first find the slope of a line: S=Y/X
S=slope of the line
Y=the Y-difference between the two points.
X=the X-difference between the two points.

Now that you have the slope, you need to get the Y-value at the X-position:
Y=SX+Y1
Y1 is the Y-value of the first vertex.
X= the X-distance on the line the soldier is from vertex1.

You MUST keep track of which vertex is the first one. I would use the lower numbered one so that Y1 is, for instance, from Vertex(0,0) and Y2 is from Vertex(0,1) or whatever as long as you are consistant.

Do that with two lines of the face your soldier is on and take the average of the two Y-values you get, and ta-dah, you have an interpolated Y-value.

To be sure you understand what I mean, I'm going to ramble on some more....
Each face has 3 verteces that make it up. Use some simple X,Z tests to determine which face it is. Most mesh builders have the same pattern for a plane so that the hypotanous side of the triangle is always sloping the same way, however, you may want to be sure before you stick to that idea.... I'm sure you can figure out how to find the face once you know that. Use the same vertex for the two calculations above as the start vertex; I would use the vertex that is where the 90deg place is (can't remember the name). And for the "other" vertex use the other two verteces, one for each calculation set.

Man! I love long drawn-out explainations!

The fastest code is the code never written.
Back to top
Profile PM Email Website
Garion
18
Years of Service
User Offline
Joined: 7th Dec 2007
Location: Poland
Posted: 14th Apr 2010 21:01
Link
GG I mean units, like RTS units or soldiers

Hawkblood Thanks for explaining. I've tried that and the problem was here:

Do that with two lines of the face your soldier is on and take the average of the two Y-values you get, and ta-dah, you have an interpolated Y-value.

The x's height and z's height interpolated well but player's height is not equal to average of them... OR I'm doing it wrong. I'll try again now, but...

Ah, maybe I'll draw some more explanations then
Back to top
Profile PM Email
Hawkblood
16
Years of Service
User Offline
Joined: 5th Dec 2009
Location:
Posted: 14th Apr 2010 22:11
Link
You MUST be sure of the face orientation to do it properly. The most likely prolem is that you are not using the verteces of the same face. Check your orientation.

The fastest code is the code never written.
Back to top
Profile PM Email Website
Garion
18
Years of Service
User Offline
Joined: 7th Dec 2007
Location: Poland
Posted: 14th Apr 2010 22:42 Edited at: 14th Apr 2010 22:56
Link
To be honest, I've done it a bit differently but the result should be the same. I had a 100x100 mesh (square polys) so I created an 100x100 array and using sparkys collision precalculated the heights at all these 10000 points.

So I had an array: map_height(100,100) and the problem really is finding the height of a point like (56.65,11.12), thus using interpolation. Aurea dictum, my own stupidity

Using the array, I think the function is supposed to look something like this:

function get_height(realx as float,realz float)

x=realx*0.01
z=realz*0.01
next_x = x+1
next_z = z+1

ax = realx/(x+1)*100
az = realz/(z+1)*100

h1= map_height(x,y)+ax*map_height(next_x,next_y)
h2= map_height(x,y)+az*map_height(next_x,next_y)

height = (h1+h2)*0.5

endfunction height

But that's not the right method, I'm quite sure *pushes the limits of his rusty brain wheels*
Back to top
Profile PM Email
Hawkblood
16
Years of Service
User Offline
Joined: 5th Dec 2009
Location:
Posted: 15th Apr 2010 05:36 Edited at: 15th Apr 2010 05:40
Link
Your not using the formula corectly.

Use the pic I uploaded as a reference.
Assume that A, B, and C are your positions that represent the verteces of the "face" that Mr. Stickman is on.
Stick.x=where on the X-axis Mr. Stickman is
Stick.y=where on the Y-axis Mr. Stickman is
Stick.z=where on the Z-axis Mr. Stickman is

SM.x=Stick.x-A.x
SM.z=Stick.z-A.z
**** All values of the verteces that follows will be actual not relative****
Find the slope of line AB: S1=(B.y-A.y)/(B.x-A.x)
Use that slope to find the AB-line's Y-value: Y1=S1*SM.x+A.y

Find the slope of line AC: S2=(C.y-A.y)/(C.z-A.z)
Use that slope to find the AC-line's Y-value: Y2=S2*SM.z+A.y

Stick.y=(Y1+Y2)/2.0

EDIT: Had to make some corrections, is anyone noticed.

The fastest code is the code never written.
Back to top
Profile PM Email Website
Garion
18
Years of Service
User Offline
Joined: 7th Dec 2007
Location: Poland
Posted: 28th Apr 2010 15:57
Link
Hawkblood

Sorry for the bump/delay. Just wanted to tell that I modified your version a bit and it works perfectly

Thank you VERY much! Problem solved. And it works 99999 times faster than using sparkys collision for every object
Back to top
Profile PM Email
Hawkblood
16
Years of Service
User Offline
Joined: 5th Dec 2009
Location:
Posted: 30th Apr 2010 17:29
Link
Glad to help.

The fastest code is the code never written.
Back to top
Profile PM Email Website
Back to top

Login to post a reply

Server time is: 2026-07-26 02:36:43
Your offset time is: 2026-07-26 02:36:43