Java-Gaming.org Hi !
Featured games (87)
games approved by the League of Dukes
Games in Showcase (649)
Games in Android Showcase (181)
games submitted by our members
Games in WIP (700)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
   Home   Help   Search   Login   Register   
  Show Posts
Pages: [1] 2 3 ... 77
1  Game Development / Game Mechanics / Re: Best data structure for triangle collision meshes on: 2016-01-21 20:03:04
You pretty much have it right.
 - Yes.
 - (just to be explicit) Specifically the minimal AABB that fits the children's (you knew this)
 - Minimize node area, perimeter and overlap while maximizing number of children per node
 - R-Tree: split an overflowing node in place; R*-Tree: when a node overflows, first attempt to remove some of it's children and insert them elsewhere before having to do an actual split

The good news is that the STR construction handles splitting, indeed probably better than the R*-Tree topological-sort-like split method.
No other splitting needs to be delt with, since your tree would (hopefully) be static.

EDIT: found my old rtree/str post here: http://www.java-gaming.org/topics/what-i-did-today/33622/msg/335424/view.html#msg335424
_basil responds further down the page.
2  Game Development / Game Mechanics / Re: Best data structure for triangle collision meshes on: 2016-01-21 19:41:39
I would have a separate datastructure for dynamic objects if possible, at least when auditioning the R-Tree structure, as the insertion and deletion functions are where the bulk of the complexity is. The 2 query types could be potentially done in parallel as well, although they might be too fast to gain much.
3  Game Development / Game Mechanics / Re: Best data structure for triangle collision meshes on: 2016-01-21 19:33:46
Quote
If you know of a small minimal implementation of R* trees that'd probably help me a lot.

The only ones I know of aren't at all minimal (think enterprise-grade...): [1], [2] and are mostly intended for stuff like geospatial applications.

All you would need is two functions: bulk-load construction (since you have pre-known, static data, no insertion/deletion functionality is required) and intersection query, correct?
4  Game Development / Game Mechanics / Re: Best data structure for triangle collision meshes on: 2016-01-21 16:57:07
Quote
Do you have any good resources for them?

Mostly just the paper(s) cited on wikipedia: The R* Tree

I forgot that STR bulk loading works on  regular R-trees, so I'd just start there; here's that paper: STR
You know it's good if NASA came up with it!  Pointing
5  Game Development / Game Mechanics / Re: Best data structure for triangle collision meshes on: 2016-01-21 03:03:26
R-Tree? Should be faster than  Quad/Oct-trees I believe, it's at least highly tune-able. Look at the R* variant with it's Sort-Tile-Recursive construction method since you can exploit the fact that your data is static. Those are stupid fast for spatial queries in my experience.
6  Discussions / Miscellaneous Topics / Re: What I did today on: 2016-01-06 14:23:25
You should link were it's from: https://github.com/adonaac/blog/issues/9
7  Discussions / Miscellaneous Topics / Re: Benchmark this JAR - yes, a Vangard demo! on: 2015-12-10 22:57:48
CPU-Z is reporting that it is single channel. That's annoying.
8  Discussions / Miscellaneous Topics / Re: Benchmark this JAR - yes, a Vangard demo! on: 2015-12-09 20:17:25
i7 4700MQ 2.4 GHz
Intel HD Graphics 4600
1080p

zoom 1:
  logic 0-2 ms
  render 63 ms

zoom 10:
  logic 0-2 ms
  render 28 ms

zoom 75:
  logic 1-2 ms
  render 35 ms

Logic times display as '0' most of the time, so no problems there. Task manager shows all 8 (virtual) cores at about 1/4 to 1/3 usage, with one of them at 3/4 (probably hosting the render thread).

I couldn't get the process to pick the GT 755M for the GPU unfortunately.
9  Game Development / Newbie & Debugging Questions / Re: String processor? on: 2015-12-01 01:20:06
I, and I'll bet others, have no idea where you extrapolated that meaning from that quote. OP needs to define an actual problem.
10  Discussions / General Discussions / Re: What version of Java do you use on: 2015-11-16 22:54:08
Kotlin.  Pointing
11  Discussions / Miscellaneous Topics / Re: What I did today on: 2015-11-14 03:06:03
Quote
Posts Link

But that's sonic...
12  Discussions / General Discussions / Re: Library Performance vs. Stupid Mistake Friendly on: 2015-11-08 07:40:21
For your specific example, caching and passing the current thread id through underlying calls would all but remove the overhead.
13  Discussions / General Discussions / Re: Programmer jokes on: 2015-11-04 19:42:04
That was on page two.

Thread.gc();
14  Discussions / General Discussions / Re: JGO IDE Survey on: 2015-11-03 19:03:41
No love for Emacs?

I haven't used it for Java yet, but I'll probably be trying this, which looks interesting. It'd be nice if I could stay inside Emacs for everything.
15  Discussions / Miscellaneous Topics / Re: Battlestation Thread on: 2015-10-29 22:13:31
This thread again, huh?

I haven't changed much from this picture, although I now have a laptop as primary in place of the keyboards and have the big monitor up and behind it.

16  Game Development / Newbie & Debugging Questions / Re: Collision detection using the Rectangle's intersects() method. on: 2015-10-23 01:33:01
If that's really what you want:
a.intersects(b) && !(a.contains(b) || b.contains(a))



17  Discussions / Miscellaneous Topics / Re: What I did today on: 2015-10-20 14:28:08
Opiop: "yep, collision detection works"
18  Discussions / Miscellaneous Topics / Re: What I did today on: 2015-10-17 18:55:18
Found what I'm going to call the new go-to "Juice it" video:

<a href="http://www.youtube.com/v/pmSAG51BybY?version=3&amp;hl=en_US&amp;start=" target="_blank">http://www.youtube.com/v/pmSAG51BybY?version=3&amp;hl=en_US&amp;start=</a>
Direct link
19  Game Development / Performance Tuning / Re: Pathfinding for tons of creatures on: 2015-10-13 04:54:35
Quote
Instead, I should be limiting how often an animal updates its path

That is exactly the point of caching, which it doesn't sound like you're doing if you're recalculating on each frame.
20  Game Development / Performance Tuning / Re: Pathfinding for tons of creatures on: 2015-10-13 00:54:31
It is very possible. Thousands at once are quite possible.

First off: I hope you aren't computing every entity's path each frame. Cache them. Only recompute paths when required (such as the entity reached it's destination and needs a new one, or something stepped in front of it, etc). Only allow up to a certain number of paths to be computed per frame, others will simply have to wait until next frame. This smooths out lag spikes.
Also: what algorithm are you using? Is it a known one or homebrewed?
21  Games Center / WIP games, tools & toy projects / Re: Vangard on: 2015-10-09 19:49:22
Clearly you should add programmers to the village so they can write your game for you.
22  Game Development / Newbie & Debugging Questions / Re: New to the Java scene and looking to begin developing games on: 2015-10-09 00:34:18
Can recommend Processing. Especially since version 3 just came out, it has some nifty things: https://vimeo.com/140600280
23  Game Development / Shared Code / Re: Extremely Fast sine/cosine on: 2015-10-08 14:35:31
@Roquen
From what I can gather HotSpot wouldn't be allowed to emit FMA ops because they yield different results:
http://stackoverflow.com/questions/22562510/does-java-strictfp-modifier-have-any-effect-on-modern-cpus#comment34358602_22562510
Related: http://mail.openjdk.java.net/pipermail/hotspot-compiler-dev/2015-January/016809.html
24  Game Development / Shared Code / Re: Extremely Fast sine/cosine on: 2015-10-08 05:34:34
This particular benchmark is for the sin(t + xi,yj) scenario, as presented by agentd.
The 2nd 'kind' of calculation was to implement roquen's insight on how to algebraically optimize this scenario, as opposed to making the naive formula fast.
You'll also notice that the sumOfAngles technique's speed is almost completely independent of the speed of the underlying trig functions. So java stdlib is used for accuracy.
25  Game Development / Shared Code / Re: Extremely Fast sine/cosine on: 2015-10-08 03:12:54
Yep, from 50.8 us/104 ops to 46.4. But with Math.floor its about 90.

Current code, hopefully last one for today: http://pastebin.java-gaming.org/b2bda6b7a361e
26  Game Development / Shared Code / Re: Extremely Fast sine/cosine on: 2015-10-08 01:50:10
The real thing to notice is that the sumOfAngles (both variants) were using Riven's trig. Using Math.sin/cos it has very little error:

sumOfAngles
DoubleSummaryStatistics{count=20000, sum=0.025140, min=0.000000, average=0.000001, max=0.000004}

sumOfAnglesSOA
DoubleSummaryStatistics{count=20000, sum=0.025140, min=0.000000, average=0.000001, max=0.000004}

agent
DoubleSummaryStatistics{count=20000, sum=0.250961, min=0.000000, average=0.000013, max=0.000083}

riven
DoubleSummaryStatistics{count=20000, sum=5.018816, min=0.000000, average=0.000251, max=0.000762}


Speed is basically unaffected, as expected:


N = 10_000

Benchmark                 Mode  Samples    Score  Score error  Units
b.Test.scalarAgentMath    avgt       10   50.894        1.278  us/op
b.Test.scalarJavaMath     avgt       10  876.978        6.797  us/op
b.Test.scalarRivenMath    avgt       10   21.657        0.129  us/op
b.Test.sumOfAngles        avgt       10   14.239        0.094  us/op
b.Test.sumOfAnglesSOA     avgt       10    4.663        0.041  us/op


I probably should have remembered to do this earlier.
27  Game Development / Shared Code / Re: Extremely Fast sine/cosine on: 2015-10-08 01:39:16
Output of abs(expected - actual) across whole array, at N = 1_000_000:
(Ignore DoubleXX, all the comp is done in single precision)


agent
DoubleSummaryStatistics{count=2000000, sum=33.722636, min=0.000000, average=0.000017, max=0.000083}

sumOfAnglesSOA
DoubleSummaryStatistics{count=2000000, sum=745.938334, min=0.000000, average=0.000373, max=0.001289}

riven
DoubleSummaryStatistics{count=2000000, sum=488.212535, min=0.000000, average=0.000244, max=0.000762}

sumOfAngles
DoubleSummaryStatistics{count=2000000, sum=745.938334, min=0.000000, average=0.000373, max=0.001289}
28  Game Development / Shared Code / Re: Extremely Fast sine/cosine on: 2015-10-08 01:30:00
http://stackoverflow.com/questions/24723527/what-does-openjdk-jmh-score-error-exactly-mean
29  Game Development / Shared Code / Re: Extremely Fast sine/cosine on: 2015-10-08 00:30:49
Hmm, things definitely get more interesting at lower input sizes. That caching-[regression?] is pretty disappointing.

http://pastebin.java-gaming.org/3b2bd5a7b3a16


N = 1_000_000

Benchmark                 Mode  Samples      Score  Score error  Units
b.Test.scalarAgentMath    avgt       10   5433.443       24.239  us/op
b.Test.scalarJavaMath     avgt       10  89490.975      592.976  us/op
b.Test.scalarRivenMath    avgt       10   2642.146       60.246  us/op
b.Test.sumOfAngles        avgt       10   3321.570       23.815  us/op
b.Test.sumOfAnglesSOA     avgt       10   3300.369       46.918  us/op

N = 100_000

Benchmark                 Mode  Samples     Score  Score error  Units
b.Test.scalarAgentMath    avgt       10   507.983        4.833  us/op
b.Test.scalarJavaMath     avgt       10  8739.558       67.833  us/op
b.Test.scalarRivenMath    avgt       10   219.087        4.151  us/op
b.Test.sumOfAngles        avgt       10   143.886       10.281  us/op
b.Test.sumOfAnglesSOA     avgt       10    70.607        3.719  us/op

N = 10_000

Benchmark                 Mode  Samples    Score  Score error  Units
b.Test.scalarAgentMath    avgt       10   51.648        0.908  us/op
b.Test.scalarJavaMath     avgt       10  903.191        4.800  us/op
b.Test.scalarRivenMath    avgt       10   22.001        0.099  us/op
b.Test.sumOfAngles        avgt       10   14.263        0.107  us/op
b.Test.sumOfAnglesSOA     avgt       10    4.646        0.019  us/op


I got jitwatch working and can confirm the SOA variant is using packed arithmetic.
30  Game Development / Shared Code / Re: Extremely Fast sine/cosine on: 2015-10-07 17:20:51
What was the problem exactly?

Notice the loop bounds on the old pastebin:
for (int i = 0; i < state.N; i += 4) { // derp; should be N * 4


Write those unit tests kids!


@KaiHH

Benchmark                 Mode  Samples      Score  Score error  Units
b.Test.scalarAgentMath    avgt       10   5209.268      103.278  us/op
b.Test.scalarJavaMath     avgt       10  83709.325      960.562  us/op
b.Test.scalarRivenMath    avgt       10   2654.518      266.021  us/op
b.Test.sumOfAngles        avgt       10   3174.081      396.252  us/op


@Spasi

Could I see your sumOfAngles implementation? I'm curious as to how fastMath and sumOfAngles switched places.
I'm running this on jdk1.8_05, i7 4700MQ


Latest: http://pastebin.java-gaming.org/f3b2b4d7a3b1a
Pages: [1] 2 3 ... 77
 
KaiHH (144 views)
2016-01-31 23:15:29

sci4me (151 views)
2016-01-23 21:47:05

sci4me (137 views)
2016-01-23 21:46:58

KaiHH (170 views)
2016-01-19 13:26:42

theagentd (256 views)
2016-01-05 17:10:00

ClaasJG (270 views)
2016-01-03 16:58:36

chrisdalke (260 views)
2015-12-28 06:31:21

Guerra2442 (267 views)
2015-12-25 03:42:55

Guerra2442 (267 views)
2015-12-25 03:27:21

theagentd (294 views)
2015-12-21 14:43:24
List of Learning Resources
by SilverTiger
2016-02-05 09:39:47

List of Learning Resources
by SilverTiger
2016-02-05 09:38:38

List of Learning Resources
by SilverTiger
2016-02-05 09:35:50

Rendering resources
by Roquen
2015-11-13 14:37:59

Rendering resources
by Roquen
2015-11-13 14:36:58

Math: Resources
by Roquen
2015-10-22 07:46:10

Networking Resources
by Roquen
2015-10-16 07:12:30

Rendering resources
by Roquen
2015-10-15 07:40:48
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!