Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (487)
Games in Android Showcase (112)
games submitted by our members
Games in WIP (553)
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 ... 6
1  Discussions / General Discussions / Re: Performance Test for the Voxel Thing on: 2014-08-28 14:05:15
30-33fps

AMD A10-7850K, set to 45W TDP and underclocked. Using the integrated graphics.
2  Game Development / Newbie & Debugging Questions / Re: Stuck in recursion hell! on: 2014-08-28 07:36:36
I'd suggest you move to using a queue and perform a breadth-first fill.

Tail recursion is just depth-first traversal where you use the program stack instead of explicitly using a stack object. This makes the code more succinct and maps nicely to recurrence relations, but doesn't buy you much else.

For the breadth-first fill, start by putting all sources in the queue then just dequeue and process one by one as you are now.

Edit: you can do fancier stuff with non-tail recursion, but that doesn't really apply here
3  Game Development / Shared Code / Re: Trie-based dictionary on: 2014-07-09 11:14:34
The idea was just to sort both dictionary and query so that you're working with sets of letters instead of series. Alphabetic order was just what first popped in to my head, but going in least or most popular order sounds like a good idea.

If keeping the words' strings in memory as well as trie nodes is too much then I guess this wouldn't work. I'm pretty sure it's guaranteed to be no slower than the unsorted version (with the worst case being when there are no anagrams sharing leaves) and could be a lot quicker when there are anagrams sharing nodes.
4  Game Development / Shared Code / Re: Trie-based dictionary on: 2014-07-08 15:22:40
Sure, but using the trie with sorted entries would also exclude most subsets in the same way, right?
5  Game Development / Shared Code / Re: Trie-based dictionary on: 2014-07-08 12:44:28
Did you consider sorting the characters of each word in the dictionary before building the trie? Then each node would need to additionally contain a list/set of the valid, unsorted, words. You sort the query characters and you would be searching for all subsets rather than all permutations. That's down to 2^9 queries.

I might have misunderstood what you're doing. If so, ignore this. Wink
6  Discussions / Community & Volunteer Projects / Re: game idea: "space wars" on Klein bottle surface? on: 2014-05-18 12:11:21
Actually it's pretty trivial to do this by just tweaking the way screen wrapping works. Right at the the top of the wikipedia page it shows how to write the mapping from left-side to right-side and top to bottom: http://en.wikipedia.org/wiki/Klein_bottle.

It's more fun when you make top map to left and bottom to right though. I've used that before as a quick way to model a planet's surface on a diamond. It has some nice properties where the longitudinal lines at the equator are longer than those near the poles which is a bit more realistic than the cylinder maps.
7  Game Development / Game Play & Game Design / Re: Best Way to Register Blocks/Entities on: 2014-01-19 13:57:12
Actually, I did some research and didn't find much on the subject. Would you mind giving a very brief explanation of them?
Wikipedia does a good job of explaining it, and even includes some examples in Java:
http://en.wikipedia.org/wiki/Factory_method_pattern
http://en.wikipedia.org/wiki/Abstract_factory_pattern
8  Discussions / Java Gaming Wiki / Re: Smoothing Algorithm Question on: 2013-05-31 06:55:53
One last shot on the basic sliding rectangle. Instead of smoothing the whole volume just apply the function when a cell's value is requested. Because the rays will be continuous you can still use some of the simple optimisations and slide the rectangle down the ray.

This would require three copies of the data though: the original, the sparse smoothed version, and the result.

The efficiency would then depend on how many cells are typically hit by rays between smoothing operations.
9  Discussions / Java Gaming Wiki / Re: Smoothing Algorithm Question on: 2013-05-30 10:59:00
I think we both mean rectangular function though in 3 dimensions. As a filter in the frequency domain that's ... sinc (thanks wikipedia!). This is also the Haar scaling function, so the roughly opposite effect of the Haar wavelet that turns discontinuities into high value spikes.

I'm still only thinking smoothing, but since the filter is compact you can process the data in overlapping pieces and ignore the edge values. I'd guess this would be in "run overnight" territory even for very large data sets, much less for less than a billion cells.


10  Discussions / Java Gaming Wiki / Re: Smoothing Algorithm Question on: 2013-05-30 07:08:34
If you use a rectangular filter (i.e. all cells are equally weighted) then just calculating the differences as the block shifts should be the easiest to program and reasonably efficient.

If you're doing a non-rectangular filter then philfrei's suggestion of performing it as a convolution is probably the right way. This requires a 3D Fourier transform, but a quick Google gives http://www.mathworks.com/matlabcentral/fileexchange/24504

Which should run in Octave if you don't have Matlab.
11  Discussions / Java Gaming Wiki / Re: Smoothing Algorithm Question on: 2013-05-28 13:19:09
As the 100x50x50 block slides around you don't need to recalculate all the values. A simple optimisation is to only calculate the next 50x50 slice that it is shifting to then update the previous mean.

If you can afford to have a duplicate of the data for writing to then you can do better again. Just calculate the mean for whole block once for the very first position. Then replace the remaining cells with their contribution to  change in mean (the difference between their value and one 50 or 100 places distant, depending on their axis). Then you should be able to walk the block around using only 50 (or 100) calculations per step.
12  Game Development / Newbie & Debugging Questions / Re: AI search and Java on: 2013-03-17 14:32:53
What you're doing sounds right to me so it's probably just a bug.

Are there any other side effects on the board from adding a piece, like removing opponents pieces, that the undo might get wrong? Is the move being used for move/undo being modified at all during the search?
13  Game Development / Newbie & Debugging Questions / Re: AI search and Java on: 2013-03-17 08:29:24
Quote
To speed up things I implemented a makemove/undomove within the function
This will work fine, so long as you are doing depth-first search (which you are, because of the recursive calls).

Quote
due to the nature of Java not passing objects by reference
Typo? You mean Java always passes by reference. So no new copy of an object is made by default.

Quote
and I don't pass the board object as a parameter to itself
This is a little confusing. Does it mean that the search function is within the board class itself? Or that a single static board object exists?

Regardless, I'd have player objects decide their own moves and have any search functions in their classes. These methods should pass a board around as a parameter.

All you need to do is put your move and undo-move before and after each recursive call, as in (pseudocode):
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
double search(Board board, int depth)
  if( depth=0 )
    return heuristic(board)
  else
     maxValue = 0
     for each move in children(board)
       move.makemove(board)
       maxValue = max(maxValue,search(board,depth-1)
       move.undomove(board)
     return maxValue
14  Game Development / Performance Tuning / Re: YAAST (Yet another AStar Thread) on: 2013-03-07 20:47:22
The speed issue is most likely caused by using a priority queue for the closed "list". This should just be a set of closed nodes that you check contains() on. You'll also find lots of posts around here that describe how to make your own set using arrays of booleans, since you're just exploring a grid. Though that's probably an unnecessary optimisation.

For the over-exploration, that's because you're estimating the distance left using the Euclidean distance but you don't allow diagonal moves. So it greatly underestimates it. Try using the closer estimate of:
1  
n.h = Math.abs(startX - tarX) + Math.abs(startY-tarY);

which you almost had, an then commented out  Wink
15  Game Development / Newbie & Debugging Questions / Re: Neural Network Help on: 2012-11-14 08:02:01
One thing is that it looks like the number of nodes in your hidden layer(s) are the same as in your input layer. Two nodes probably won't be enough to represent the XOR function - try 3 or more.

Also, I've never heard of any value in more than two hidden layers and I'm pretty sure that theoretically two is sufficient for any mapping from inputs to outputs (though the layers might have to be large in some cases).
16  Game Development / Performance Tuning / Re: Iterate each element of a collection randomly once only on: 2012-06-14 18:18:25
Quote
My hunch seems correct, if the interval is a prime number then a modified version of the algorithm I stated seems to work for all the testing I have performed. I will still look at the other alternatives suggested to see which gives the best speed / memory usage / randomness compromise.
The interval and length of array have to be relatively prime.

So if the interval is prime, then it also has to not be a factor of the array length. An easy way would be to make the array length a power of two then use any prime number >= 3 as the interval.
17  Game Development / Artificial Intelligence / Re: Is there a search algorithm for this? on: 2011-08-08 21:28:04
The Java implementation of FF posted there is actually very slow - I think it was just made for educational purposes. FF isn't optimal but usually gives pretty reasonable results and optimality shouldn't matter for game levels since a few extra tasks won't hurt. Graphplan is optimal but if the problem is unsolvable there is no guarantee it will terminate.

The most popular heuristics for forward-searching planners are based on a relaxed planning graph. Basically you solve the whole problem using actions with the delete effects removed, and use the length of that solution as the heuristic distance for the actual problem. It works remarkably well. That's what FF is using but with some greedy hill-climbing. HSP also uses it but isn't optimal when actions have more than a single useful effect.

STRIPS is pretty much just a subset of PDDL and they're both just used to describe a problem. There are tons of planners out there that can solve them once you've got it in that representation. Check out the annual planning contest that's part of ICAPS.
18  Game Development / Game Mechanics / Re: Generating unique random numbers. on: 2011-08-01 09:30:56
It might be easier to first generate an ordered list of N unique numbers that are between A and B, and then take randomly from that (or shuffle it after it is generated).

The ordered list can then be thought of as N+1 "gaps" between each number, where each gap is >= 1 and the sum of the gaps is B-A. If you can work out what the probability of each gap size is then you could create the list recursively:

1  
2  
3  
4  
5  
6  
List gaps(int n, int a, int b){
  if(n == 1)
      return {random(b-a)};
  int nextGap = randomGap(n,a,b);
  return {nextGap} + gaps(n-1,a+nextGap,b);
}


I don't know what the probability distribution of "randomGap" should be but I bet a statistician or wikipedia will.
19  Game Development / Game Mechanics / Re: Help implementing path finding. on: 2011-06-29 06:56:11
Because the horizontal and diagonal moves both reduce the Chebyshev distance by the same amount (1), it just comes down to the ordering of the neighbours. I'd guess that your getNeighbours() method returns the horizontal move first and in case of ties your open list returns the earlier node.

One work-around is to add a penalty value in addition to f and g. Say, for each consecutive horizontal move add a 0.001 penalty. Just make sure that the penalty values for an entire path never add up to more than the cost of one move.
20  Game Development / Newbie & Debugging Questions / Re: Tiled Maps, or Position maps on: 2011-05-23 22:54:13
I haven't done a lot with collisions, but it may be better to divide the image up into more managable sections. When you place a building, only check collisions with the image for the section that the image is being placed in. If you're placing a building at 100x 89, there is no point to see if it collides with a point at 100000 x 89.

That's pretty standard, and what I meant by "grid-based index". You need to check not only the same section, but also adjacent sections (in case your entity is right near the boundary between two).
21  Game Development / Newbie & Debugging Questions / Re: Tiled Maps, or Position maps on: 2011-05-22 22:54:00
I've just gone through exactly the same process. The solution I used was to create maps using tiles of terrain and then to allow per-pixel positioning and movement of entities on top of it. Each tile contains all its own per-pixel information that can be queried when an entity moves over it, but because tiles are being reused throughout the map it doesn't suffer the memory issues of an explicit huge 2D image.

From each entity's perspective the map is not tiled. Collision detection is done using a grid-based index that is independent of the underlying map.

I think the practical alternative to a tiled map is to use polygons to represent chunks of terrain. The only reason I didn't go down that path is that I couldn't think of a nice way to render terrain polygons. One plus of this approach is that you can reuse some of the polygon-based path finding code people have put on these forums (was it CommanderKeith?).
22  Games Center / Archived Projects / Re: Wizards of Yore on: 2011-03-30 15:14:02
I hope it's ok to use this thread for bug reporting. I got another one: on turn 2 I used Dark Power to kill all three enemy wizards. While the "Play again?" dialogue was open one of the dead (and invisible) wizards continued casting for several turns in the background.

Also, if a wizard is in a castle the AI won't move creatures toward them. Maybe not a bug?

First turn, cast vengeance killing top right wizard:
Starting 4 player game.
NEXT WIZARD
Exception in thread "Thread-9" java.lang.NullPointerException
   at org.newdawn.chaos.game.ChaosSession.nextPhase(Unknown Source)
   at org.newdawn.chaos.game.ChaosSession.nextTurn(Unknown Source)
   at org.newdawn.chaos.ai.AIWizard.doCasting(Unknown Source)
   at org.newdawn.chaos.game.ChaosSession.update(Unknown Source)
   at org.newdawn.chaos.game.ChaosGame.update(Unknown Source)
   at org.newdawn.touchapi.applet.TouchApplet.gameLoop(Unknown Source)
   at org.newdawn.touchapi.applet.TouchApplet.access$200(Unknown Source)
   at org.newdawn.touchapi.applet.TouchApplet$1.run(Unknown Source)
23  Games Center / Archived Projects / Re: Wizards of Yore on: 2011-03-29 17:54:05
Some questions/points:
- how do you leave a castle or citadel?
- are you supposed to be able to disbelieve every creature with a single cast of the spell?
- when a citadel or castle is enveloped in a gooey blob it is unaffected. Is that expected?
- creatures don't try to walk around walls
- strange things happen if you die and more than one enemy wizard is alive: once I got a message like "cannot attack own creature" every turn, and another time the game froze for about a minute before the remaining wizards played on as expected.

This is all on the applet version.

P.S. Love the game. Smiley
24  Games Center / Contests / Re: Sprite Shootout Contest Thread on: 2011-03-24 19:26:31
I tweaked Spasi's SpriteRendererPlain to use points instead of quads. It doesn't make any difference on my low end machine, but it does reduce the size of the buffers by a factor of 4. Perhaps on other machines this would make a difference.

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
57  
58  
59  
60  
61  
62  
63  
64  
65  
66  
67  
68  
69  
70  
71  
72  
73  
74  
75  
76  
77  
78  
79  
80  
81  
82  
83  
84  
85  
86  
87  
88  
89  
90  
91  
92  
93  
94  
95  
96  
97  
98  
99  
100  
101  
102  
103  
104  
105  
106  
107  
108  
109  
110  
111  
112  
113  
114  
      
private class SpriteRendererPoint extends SpriteRenderer {

           private final FloatBuffer geom;

           protected int[] animVBO;

           protected static final int BALLS_PER_BATCH = 10 * 1000;

           SpriteRendererPoint() {
               vshID = glCreateShader(GL_VERTEX_SHADER);
               glShaderSource(vshID, "#version 110\n" +
                                     "void main(void) {\n" +
                                     "     gl_Position = gl_ModelViewProjectionMatrix * gl_Vertex;\n" +
                                     "     gl_TexCoord[0] = gl_MultiTexCoord0;\n" +
                                     "}");
               glCompileShader(vshID);
               if ( glGetShader(vshID, GL_COMPILE_STATUS) == GL_FALSE ) {
                   System.out.println(glGetShaderInfoLog(vshID, glGetShader(vshID, GL_INFO_LOG_LENGTH)));
                   throw new RuntimeException("Failed to compile vertex shader.");
               }

               createProgram();

               Util.checkGLError();

               final FloatBuffer staticData = BufferUtils.createFloatBuffer(BALLS_PER_BATCH * 2);
               for ( int i = 0; i < BALLS_PER_BATCH; i++ ) {
                   staticData.put(0.0f).put(0.0f);
               }
               staticData.flip();

               staticVBO = glGenBuffers();
               glBindBuffer(GL_ARRAY_BUFFER, staticVBO);
               glBufferData(GL_ARRAY_BUFFER, staticData, GL_STATIC_DRAW);

               glEnableClientState(GL_TEXTURE_COORD_ARRAY);
               glTexCoordPointer(2, GL_FLOAT, 0, 0);
               
               glEnable(GL_POINT_SPRITE);
               glPointSize(42.0f);
               glTexEnvf(GL_POINT_SPRITE, GL_COORD_REPLACE, GL_TRUE);

               glEnableClientState(GL_VERTEX_ARRAY);
               
               System.out.println("Shootout Implementation: CPU animation + BufferData (Points)");
               geom = BufferUtils.createFloatBuffer(BALLS_PER_BATCH * 2);
           }

           @Override
           public void updateBallSize(){
               glPointSize(ballSize);
           }

           protected void putBall(final FloatBuffer geom, final float x, final float y) {
               float half = ballSize/2;
               geom.put(x+half).put(y+half);
           }

           public void updateBalls(final int count) {
               super.updateBalls(count);

               final int batchCount = count / BALLS_PER_BATCH + (count % BALLS_PER_BATCH == 0 ? 0 : 1);
               if ( animVBO != null && batchCount == animVBO.length )
                   return;

               final int[] newAnimVBO = new int[batchCount];
               if ( animVBO != null ) {
                   System.arraycopy(animVBO, 0, newAnimVBO, 0, Math.min(animVBO.length, newAnimVBO.length));
                   for ( int i = newAnimVBO.length; i < animVBO.length; i++ )
                       glDeleteBuffers(animVBO[i]);
               }
               for ( int i = animVBO == null ? 0 : animVBO.length; i < newAnimVBO.length; i++ ) {
                   newAnimVBO[i] = glGenBuffers();
                   glBindBuffer(GL_ARRAY_BUFFER, newAnimVBO[i]);
               }

               animVBO = newAnimVBO;
           }

           public void render(final boolean render, final boolean animate, final int delta) {
               int batchSize = Math.min(ballCount, BALLS_PER_BATCH);
               int ballIndex = 0;
               int vboIndex = 0;
               while ( ballIndex < ballCount ) {
                   glBindBuffer(GL_ARRAY_BUFFER, animVBO[vboIndex++]);

                   if ( animate )
                       animate(ballIndex, batchSize, delta);

                   if ( render ) {
                       glVertexPointer(2, GL_FLOAT, 0, 0);
                       glDrawArrays(GL_POINTS, 0, batchSize);
                   }

                   ballIndex += batchSize;
                   batchSize = Math.min(ballCount - ballIndex, BALLS_PER_BATCH);
               }
           }

           private void animate(final int ballIndex, final int batchSize, final int delta) {
               animate(geom, ballIndex, batchSize, delta);

               // This throws OUT_OF_MEMORY error on AMD.
              //glBufferData(GL_ARRAY_BUFFER, geom.capacity() * 4, GL_STREAM_DRAW);
              //glBufferSubData(GL_ARRAY_BUFFER, 0, geom);

               final int i = ballIndex / BALLS_PER_BATCH;
               glDeleteBuffers(animVBO[i]);
               animVBO[i] = glGenBuffers();
               glBindBuffer(GL_ARRAY_BUFFER, animVBO[i]);
               glBufferData(GL_ARRAY_BUFFER, geom, GL_STREAM_DRAW);
           }
       }
25  Games Center / Contests / Re: Sprite Shootout Contest Thread on: 2011-03-23 17:57:50
I get the same results: 2800 to get 60 fps. This should be the new version (not cached) as it accepted 'z' as keyboard input.
26  Games Center / Contests / Re: Sprite Shootout Contest Thread on: 2011-03-22 21:50:14
I get strangely low results from libgdx. Radeon 4350; Phenom II X2 550; Ubuntu 10.10; proprietary Catalyst drivers.

Slick2D: 4000
Artemis: 5000
libgdx: 2800
Spasi's OpenGL: 6100
Spasi's OpenGL 16x16: 65000

@60 fps
27  Game Development / Shared Code / Re: Astar Pathfinding on: 2011-01-20 15:23:44
Why bother with sqrt or max/min?  Euclidean distance squared is an equivalent metric to euclidean distance. (if a*a > b*b, then |a| > |b|)
The problem is that you actually need to combine the results of the heuristic with the cost so far. So if just using the square of the heuristic you'd have f(x) = g(x) + h(x)*h(x), which for heuristic values greater than 1 would make the search tend to a best-first (and the heuristic is non-admissible).

Taking the square of the cost so far doesn't fix it either, because g(x)*g(x) + h(x)*h(x) still doesn't have the same metric properties as g(x) + h(x).
28  Game Development / Shared Code / Re: Astar Pathfinding on: 2011-01-20 09:46:22
Quote
So yeah, in your case a Euclidean heuristic is necessary.
There are other admissible heuristics. E.g. max(abs(x - x0), abs(y - y0)).

True, bad wording on my part.

Is there a mistake in the second heuristic though? Won't
1  
int heuristic = max + (dx + dy - max) / (2 * max);

just be equal to max because of integer rounding?

With diagonal moves costing sqrt(2) rather than 1, perhaps it could be:
1  
2  
3  
4  
int dx = x - x0; if (dx < 0) dx = -dx;
int dy = y - y0; if (dy < 0) dy = -dy;
int max = dx > dy ? dx : dy;
double heuristic = max - (dx + dy - max) + Math.sqrt(2) * (dx + dy - max);

Ok, so not coded to be efficient any more, but it dominates the Euclidean distance this way and is guaranteed to expand fewer nodes.
29  Game Development / Shared Code / Re: Astar Pathfinding on: 2011-01-19 15:09:22
Hey thx for the explication Jono. I guess I will add Euclidian.

Now I'm using an Heuristic that is always a bit bigger than the shortest path, won't it be slower if I use one that is always smaller?

Yep, it'll be slower but it will be guaranteed to find the shortest path. I had a play with the demo to find an example of what I was talking about:



The one on the left is what is returned by the Manhattan heuristic (current implementation). The one on the right is a shorter path that isn't found. Notice the early diagonal move that confuses the search on the left.
30  Game Development / Shared Code / Re: Astar Pathfinding on: 2011-01-19 14:57:17
I'm aware that Manhattan doesn't return necessarly the best path, but I failed to see why Euclidean would return the best one.

This pathfinding is suppose to find a ''good'' path even with non uniform movement cost in theory but I don't think it is the case with the current Heuristic.

To guarantee the shortest path the heuristic has to always be lower than the actual distance. So an ideal heuristic is one that is as high as possible but never quite goes over the actual distance to the goal.

For the grid-world the difference between Manhattan's estimate an the actual distance is worst when the goal is on a direct diagonal path from the current location. The Euclidean distance will be exactly the same as the real distance in this case, and will be lower than the actual distance in all other cases. Because the Euclidean distance gets estimates that are close to the real distance, the search will expand fewer nodes than a heuristic that gives lower values (e.g. a stupid heuristic that always guesses zero will still give the best path, but will expand lots more nodes).

What you might see with the Manhattan heuristic is that the search will try a diagonal move that will make a big jump in the heuristic, and then never have a chance to come back to try a horizontal or vertical move that is actually on a shorter path.
Pages: [1] 2 3 ... 6
 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

TehJavaDev (15 views)
2014-08-28 18:26:30

CopyableCougar4 (25 views)
2014-08-22 19:31:30

atombrot (38 views)
2014-08-19 09:29:53

Tekkerue (33 views)
2014-08-16 06:45:27

Tekkerue (32 views)
2014-08-16 06:22:17

Tekkerue (20 views)
2014-08-16 06:20:21

Tekkerue (29 views)
2014-08-16 06:12:11

Rayexar (66 views)
2014-08-11 02:49:23

BurntPizza (42 views)
2014-08-09 21:09:32

BurntPizza (34 views)
2014-08-08 02:01:56
List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06

List of Learning Resources
by SilverTiger
2014-07-31 11:54:12

HotSpot Options
by dleskov
2014-07-08 01:59:08
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!