Java-Gaming.org Hi !
Featured games (85)
games approved by the League of Dukes
Games in Showcase (612)
Games in Android Showcase (172)
games submitted by our members
Games in WIP (658)
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: What projects are you guys working on? How's progress going? on: 2015-07-01 12:09:05
Automatic interactive story generator. You give it a world and it makes a story that a user can branch at any point.

 Progress is.. progressing. As it has for the last 4 years or so. I hope to have an interactive text version for ~2 minute long stories working by the end of the year.
2  Discussions / Miscellaneous Topics / Re: advanced 'Knapsack problem' on: 2015-04-22 12:46:33
This also sounds like something you could potentially solve with a theorem prover like Z3.

Yeah, this is an SMT problem http://en.wikipedia.org/wiki/Satisfiability_modulo_theories. What you are doing is called constraint programming.

If you really want to roll your own, I'd do it this way:
- first make a solver that finds a solution to the hard (boolean) constraints
- generate a single valid solution
- traverse the space of valid solutions, testing the overall value of the soft constraints as you go
- after some time or after exhausting the search space, return the best result found so far

From your description of the problem it shouldn't be too hard to define a function that takes a valid solution and generates similar, valid solutions for the traversal, so this kind of approach should be ok.

If you can make the first step non-deterministic then keep repeating with greedy searches from new valid start points -- this is much less prone to getting stuck in local optima than evolutionary algorithms and will be quicker too.
3  Game Development / Shared Code / Re: Curve fitting on: 2015-04-01 16:08:27
I find the easiest way to understand the DFT is as least squares: http://en.wikipedia.org/wiki/Linear_least_squares_%28mathematics%29.

You're finding the best coefficients for a set of sinusoids so their sum is closest to your data. By using sufficient sinusoids of different frequencies these form a basis for all 1D signals, so you can get a perfect answer.

The X in that page are all the sinusoids as a matrix (one per column).
beta are the coefficients -- they're complex so you get magnitude and phase.
y is the data (your 1D signal).
4  Discussions / Miscellaneous Topics / Re: What I did today on: 2015-03-01 12:56:13
38.3 in average.

(1.0-0.001)^999 = 0.368063488

999 adjacent pairs, with each second item having a 1/1000 chance of matching the prior. Sorry, couldn't hold back.
5  Game Development / Game Play & Game Design / Re: Game to visit all squares without overlapping -- Squarenigma on: 2015-02-24 20:42:23
What the player is doing in that is making a Hamiltonian path in the grid, with fixed start and end points.

That can help a search find things like this: http://gamejolt.com/games/puzzle/hamiltonian-path/28779/ which is pretty close. A similar old game (from 1857): http://mathworld.wolfram.com/IcosianGame.html.
6  Discussions / Miscellaneous Topics / Re: What I did today on: 2015-02-16 22:26:51
I finally have a solid initial implementation of a Goal planning system. It allows for entities to have goals and subgoals and to replan as circumstances change. A lot of GOAP material available is fiarly complicated from an implementation side, and it took a while for me to get to a simpler system that meets my needs.

I worked on a planning system too, but mine's overly complicated.

Today I fixed some bugs exposed by the fall-in-love and decide-sexuality actions.
7  Discussions / General Discussions / Re: What's your day job? on: 2015-02-16 16:24:35
I design algorithms and do data analysis for a biotech startup. It pays the bills but there's always the temptation to try and get in to enterprise stuff or finance.
8  Game Development / Game Play & Game Design / Re: The impossible 15-Puzzle on: 2015-02-12 21:52:02
My apologies, there was a bug after all. Using "0" to represent the gap makes the indexing a bit confusing and the even/odd state check was wrong.

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  
   /**
    *
    * @param state A 16-length array of tiles for each position. Tile "0" is the gap.
    * @return Whether this state can reach [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0] by sliding tiles.
    */

   public static boolean isSolvable(int[] state){
      //prepare the mapping from each tile to its position
      int[] positions = new int[16];
      for(int i = 0; i < state.length; i++){
         positions[state[i]] = (i+1)%16;
      }
     
      //check whether this is an even or odd state
      int row = (positions[0]-1)/4;
      int col = (positions[0]-1)-row*4;
      boolean isEvenState = positions[0] == 0 || row % 2 == col %2;
     
      //count the even cycles
      int evenCount = 0;
      boolean[] visited = new boolean[16];
      for(int i = 0; i < positions.length; i++){
         if(visited[i])
            continue;
         //a new cycle starts at i. Count its length..
         int cycleLength = 0;
         int nextTile = i;
         while(!visited[nextTile]){
            cycleLength++;
            visited[nextTile] = true;
            nextTile = positions[nextTile];
         }
         if(cycleLength % 2 == 0)
            evenCount++;
      }
      return isEvenState == (evenCount % 2 == 0);
   }

If you have code that makes a whole lot of random swaps from the goal that would be a good way to test the correctness.
9  Discussions / Miscellaneous Topics / Re: What I did today on: 2015-02-12 14:02:18
For someone normal living its food and warm house and time for doing what hi love to do)
Aged 17 to 20?

At that age, you might be at uni and all you need is enough money for a roof over your head, some food and beer.

You get a little older and you want to travel. You just need enough money for a roof over your head, food, beer, a plane ticket per year and some hostel fees.

You want to go out a little more with your girlfriend or boyfriend. Roof, food, beer, travel, and a bit of entertainment each week.

You get a little older and want to have a house - no point paying rent forever. So you need to add a few thousand savings per year for a deposit.

You get a little older and have a kid. Drop the beer and travel. Roof, food, savings, family entertainment and a good education for your child.

If you want to be an indie game developer, chances are you'll have to go back through that last list and choose at least two things to throw out. That's "half a living".
10  Game Development / Game Play & Game Design / Re: The impossible 15-Puzzle on: 2015-02-12 08:52:34
One thing I should have mentioned: I was assuming the blank space would be at the bottom right. Everything above is still correct, but the rule "even number of even cycles -> solvable" holds when the blank space is at an even position (e.g. bottom right is position 16, in your other example the blank space is at position 2).

When the blank space is in an odd position, the rule is "odd number of even cycles -> solvable".

If I find time today I'll put it in code..

Edit: here you go:
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  
   
   /**
    *
    * @param state A 16-length array of tiles for each position. Tile "0" is the gap.
    * @return Whether this state can reach [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0] by sliding tiles.
    */

   public static boolean isSolvable(int[] state){
      //prepare the mapping from each tile to its position
      int[] positions = new int[16];
      for(int i = 0; i < state.length; i++){
         positions[state[i]] = i;
      }
     
      //check whether this is an even or odd state
      boolean isEvenState = positions[0] % 2 == 0;
     
      //count the even cycles
      int evenCount = 0;
      boolean[] visited = new boolean[16];
      for(int i = 0; i < positions.length; i++){
         if(visited[i])
            continue;
         //a new cycle starts at i. Count its length..
         int cycleLength = 0;
         int nextTile = i;
         while(!visited[nextTile]){
            cycleLength++;
            visited[nextTile] = true;
            nextTile = positions[nextTile];
         }
         
         if(cycleLength % 2 == 0)
            evenCount++;
      }
     
      return isEvenState == (evenCount % 2 == 0);
   }


Examples:
Is the goal state solvable?
1  
System.out.println(isSolvable(new int[]{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0}));
"true"

Is one move from the goal state solvable (having moved tile 15)?
1  
System.out.println(isSolvable(new int[]{1,2,3,4,5,6,7,8,9,10,11,12,13,14,0,15}));
"true"

If you swap tiles 14 and 15 is it solvable?
1  
System.out.println(isSolvable(new int[]{1,2,3,4,5,6,7,8,9,10,11,12,13,15,14,0}));
"false"

Is your other example solvable?
1  
System.out.println(isSolvable(new int[]{1,0,3,4,6,2,11,10,5,8,7,9,14,12,15,13};));
"false"

Those are the only tests I've done, but the code seems to be bug free.
11  Game Development / Game Play & Game Design / Re: The impossible 15-Puzzle on: 2015-02-11 14:23:08
Here's how the counting goes:
- The cycle starting at 1 is (1) because it is already in the correct location. Even cycle count is still: 0
- The cycle starting at 2 is (2 6 5 9 12 14 13 *). Even cycle count is now: 1
- The cycle starting at 3 is (3). Even cycle count is still: 1
- The cycle starting at 4 is (4). Even cycle count is still: 1
- The cycle starting at 7 is (7 11). Even cycle count is now: 2
- The cycle starting at 8 is (8 10). Even cycle count is now: 3
- The cycle starting at 15 is (15). Even cycle count is still: 3

There are no more tiles that aren't in a cycle so we are done. The number of even cycles is 3, which is odd. So the arrangement is not solvable.

To get the long cycle, you look at the first tile which is 2. It's position in the arrangement is the one that 6 should be in in the solution. So 6 is next in the cycle. Then we look at tile 6. It's position in the arrangement is the one that 5 should be in in the solution. etc. When we get to the blank spot *, it is in the position that 2 should be in in the solution, but we've already processed 2 so the cycle has finished.

Hope that helps.

Edit: Your last example has cycles (1)(2)(3)(4)(5)(6)(7)(8 )(9)(10)(11)(12)(13)(14 15)(*). There is one even cycle. That's an odd number, so not solvable either.
12  Game Development / Game Play & Game Design / Re: The impossible 15-Puzzle on: 2015-02-10 20:40:50
The first link you posted with the permutations is probably the easiest test. In their first 15-puzzle example they describe the board position as:
1  
(1 11 10 9 2 3 4 7 12 13 8 * 6 15)(5 14) 

The first set of parentheses says that tile 1 is in the position that would have 11 in the solution. 11 is in the position that 10 would have. 10 is in position 9 etc.
The second set of parentheses says that tile 5 is in position 14 and tile 14 is in position 5.

You can count the size of these cycles by picking one tile to start with and just following the trail of permutations. Then picking an unvisited tile and repeating until no more tiles are left unvisited.

Count the number of cycles that have an even number of tiles in them. If this count is even, your arrangement is solvable.
13  Discussions / Miscellaneous Topics / Re: The Three Jugs Problem, Barycentric coordinates on: 2014-09-12 09:29:34
For four jars you would draw it as a tetrahedron. It has one more vertex D (for the new jar) and three more edges for pouring water from jars A<->D, B<->D, and C<->D.

For five jars you add another vertex and four more edges. Drawing it in 2D becomes a pain.
14  Game Development / Newbie & Debugging Questions / Re: Moving player tile-to-tile (A* Pathfinding finally done) on: 2014-09-08 21:10:36
(Near)zero-cost is not required, the effect is already observable if we have a parallel dirt road and paved road. Let's say the edges of the dirt road have cost 1.1 and the paved road has cost 0.9, all other edges (grass) have a cost of 2.0.

Hmm.. actually I think we're in disagreement on this bit. The heuristic distance I'd use is Manhattan*0.9, because the most optimistic estimate of the distance is that there is some direct path by paved road. A* using this will expand more nodes than if it used un-weighted Manhattan distance but it will be optimal again.

Regardless, at least the OP decided on a solution in the meantime  Grin

15  Game Development / Newbie & Debugging Questions / Re: Moving player tile-to-tile (A* Pathfinding finally done) on: 2014-09-08 15:48:16
Fair enough. I suppose the point I really wanted to make was "use an appropriate heuristic and A* will work".

If there are large zero-cost regions then it is tricky to define something more informative than h=0, but even at that limit A* just becomes Djikstra's.
16  Game Development / Newbie & Debugging Questions / Re: Moving player tile-to-tile (A* Pathfinding finally done) on: 2014-09-08 14:41:00
Oh, and A* is not guaranteed to yield the fastest path, as it is heavily biased to a path that lies on the line src→dst, it might not even visit the 'instant portal' only a few cells away (in the opposite direction). Dijkstra would handle this odd case just fine, at the cost of worse performance in the general case.

If there are portals then instead of just using Euclidean distance from A to B for the heuristic, use (Euclidean distance from A to nearest portal) + (Euclidean distance from B to nearest portal) if that is shorter. Then A* won't be incorrectly biased and will still guarantee the shortest path.
17  Discussions / General Discussions / Re: Performance Test for the Voxel Thing on: 2014-09-08 14:31:51
59Hz on an underclocked A10-7850K set to 45W TDP. 1866MHz memory.
18  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.
19  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
20  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.
21  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?
22  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
23  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.
24  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
25  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.
26  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.


27  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.
28  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.
29  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?
30  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
Pages: [1] 2 3 ... 6
 
Roquen (16 views)
2015-08-29 11:30:54

GamerC4 (26 views)
2015-08-22 20:38:50

GamerC4 (24 views)
2015-08-22 20:37:18

GamerC4 (28 views)
2015-08-22 20:37:01

Kefwar (32 views)
2015-08-22 18:07:24

GamerC4 (26 views)
2015-08-22 01:00:24

GamerC4 (38 views)
2015-08-22 01:00:17

GamerC4 (25 views)
2015-08-22 00:57:35

GamerC4 (26 views)
2015-08-22 00:56:59

BurntPizza (32 views)
2015-08-21 01:38:01
HotSpot Options
by Roquen
2015-08-29 11:33:11

Rendering resources
by Roquen
2015-08-17 12:42:29

Rendering resources
by Roquen
2015-08-17 09:36:56

Rendering resources
by Roquen
2015-08-13 07:40:51

Networking Resources
by Roquen
2015-08-13 07:40:43

List of Learning Resources
by gouessej
2015-07-09 11:29:36

How Do I Expand My Game?
by bashfrog
2015-06-14 11:34:43

List of Learning Resources
by PocketCrafter7
2015-05-31 05:37:30
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!