# Tag Info

## New answers tagged algorithm

2

Definitely a common issue! Whenever you quantize time -- which is always, in a step-wise simulation -- you need to account for these boundaries. As part of each bullet-move, you need to say something like, distanceToMove = min(velocity * time, howFarTilWeGetStopped); Which really is the same check you're already doing... just do it before rendering.

0

Another approach: Use a block cipher to "encrypt" a series of numbers from 1 to N, using a fixed key. TEA is easy to implement and fairly fast. One advantage of this approach is that if you don't like the series of "random" numbers which you get back, you can try a different encryption key and get a whole different series back.

4

Sounds like you're after something like a flood fill algorithm. Basically, something like the following algorithm (you can see other examples on the wikipedia page): 1. Add your castle to the Checklist 2. Get the first item from the Checklist 3. For each surrounding position 4. If not on Complete list 5. If `0` add to Checklist 6. If `1` ...

0

Following on vrinek's idea, how about growing the land (or shrinking the water) so parts you would originally be connected would be disconnected after the land is grown? This could be done like so: Define how much do you want to grow the land: 1 hex? 2 hexes? This value is n Visit all land nodes, and set all their neighbors up to depth n to land nodes ...

0

The whole way I was going about it is wrong. I'll answer my own question in case anybody else comes here from google. Instead of generating a whole tonne of points and appending them in one geometry shader to create lightning, the answer is to only generate each iteration of the lightning per geometry shader invocation to remove the need for having a ...

4

Here's a complete algorithm that I think should produce good results. Perform morphological erosion on the water area — that is, make a copy of the map on which each tile is considered water only if it and all of of its neighbors (or a larger area, if you have rivers wider than one tile) are water. This will result in all rivers disappearing entirely. ...

4

A quick and dirty way to identify a separate but connected body of water would be to shrink all water bodies and see if gaps appear. In the example above I think that removing all water tiles which have 2 or less water tiles connected to them (marked red) would provide you with the desirable result plus some edge noise. After you have labeled the bodies, ...

1

Create an octree and in each leaf cells put the list of all triangles from B that intersect the cell, mark at each levels whether or not the cell is empty. If one cell at any level has only 1 poly note the poly so you can stop the search early (large floor/wall triangles). You can keep sub-dividing cells until you have a reasonable number of triangles in ...

0

I think some of the answers here are missing something. I think what you really want is controls and not physics. Let me explain. Control theory explores the mathematics of systems that can sense a value, and control themselves to reach a target value. Examples of this include climate control systems, anti-lock breaking systems in cars, robots, and yes even ...

1

Computing an exact convex decomposition of a surface S is an NP-hard problem and usually produces a high number of clusters. To overcome these limitations, the exact convexity constraint may be relaxed and an approximate convex decomposition of S is instead computed. Here, the goal is to determine a partition of the mesh triangles with a minimal number of ...

0

It depends on how complex you want your AI behaviors to be. If you want the most realistic, do some research on the A* algorithm. The other easier option would most likely be depth first search. Definitely look into AI pathfinding and you should find your solution.

0

One of the programmers on my team figured out something which is good enough for our purposes. It is not exactly the same as the output of whatever X-Com is using. We take the whole tiles given to us by the Dijkstra pathfinding algorithm on the set of tiles and start at one which we can guarantee is an edge. We define a forward direction and a perpendicular ...

1

I have implemented A* pathfinding on a hexagonal grid in C# that nicely smooths paths like so (in an opensource project under the MIT License): Key portions of the code are reproduced here. void ExpandNeighbour(IDirectedPath path, NeighbourHex neighbour) { if ( ! OpenSet.Contains(neighbour.Hex.Coords)) { var cost = StepCost(neighbour.Hex, ...

3

You could look at Theta* - it's invented for exactly that purpose. Pretty much like A*, except when adding a node it tests if the new node can be reached directly from the active node's parent, and if so from that node's parent, and so on. It produces very-nearly-perfect paths in most conditions. Image is the output of my very, vey buggy C++ ...

0

Do you have an rough idea of where the gulf is? If so, you can modify your flood fill to track the number of neighbouring but unexplored cells (along with a list of visited cells). It starts with 6 in a hex map and whenever that value drops below a certain point, then you know you are hitting a "opening".

8

What you're describing is the Segmentation Problem. I'm sorry to say that it's actually an unsolved problem. But one method I would recommend for this is a Graph-Cut based algorithm. Graph-Cut represents the image as a graph of locally connected nodes. It subdivides connected components of the graph recursively such that the border between the two ...

0

Hmm... like the other answerers, I'm going to make some guesses about unclear information in the question. My assumptions: Your map is essentially 2d, and projected downward onto the walkable surface Your map is represented as a set of polygonal areas Adjacent areas share 2 (or more) vertices If that's true, one approach is to: Collect the edges of ...

1

I don't think you've got your answer since you're asking about dodging bullets (and not general avoidance ai behaviour). There are many simple ways to deal with that, each one is appropriate for a different scenario. 1- trace a ray from all bullets towards their respective progrades and with the ray magnitude (distance) relative to their velocity PLUS (or ...

1

First of all, I think the grid is pseudo-3d: 2D movement area, but create vertical lines when the height changes. Given that, check this answer, as the same principle applies.

1

Create your points so they form a solid line on a 2D plane. Walk the line starting with a point that's on ground level, for each point: If the ground is above or below the current position, add a new point, and shift the existing point and all remaining points up or down to meet the height of the ground. -Continue until all points have been touched. You ...

1

Here's a technique we've used in the past to cheat a bit on more confined hardware. It's not as pure as the more complex solutions, but has the distinct advantage of being much easier to implement and works every time. Rather than focusing on the entire puzzle, break it into smaller, uniform units. Each of these units is composed of a set number of pieces ...

1

First, find the average, minimum and maximum distance all vertices in the shirt mesh. Let those be Da, Di and Dx, respectively. Also let Dai = Di/Da and Dax = Dx/Da. Then, you test each point of your shirt mesh Ms to know if it's inside the body mesh Mb, possibly using the Jordan Curve Theorem, which is based on raycasting. Store all vertices which are ...

4

What shapes are you using? If your shapes are convex (like circles, squares, rounded rectangles), you can just draw versions of different size and clip them to a triangle whose diagonal goes from upper right to lower left. I.e., zoomed in, light-to-dark: and dark-to-light: Then clip that: And then combine the two bezels: and finally draw the ...

0

You could get a bevel effect by underlaying the cells with upscaled graduated transparencies of themselves. This can also be used to get a glow effect.

0

I just think its interesting to point out this webpage, since it helped me a lot for our proyect development. Making a sudoku with an unique solution is far away from a simple task. In the link you can find how the author (he really did a great job, its no me eh!), found several different strategies. You can have an idea to generate your own Sudoku solver. ...

-7

Run the problem backwards. Start with a filled table and cut it into pieces.

3

This is a known hard problem, determining what rectangles can be tiled with certain pieces. However, if you're building puzzles and can control the pieces, it's the opposite, constructive problem, and easier... Build a solution constructively. Take a few pieces you like, and fill the puzzle however you want. Then throw in enough single-squares to fill it ...

1

Are you on track, yes no maybe. Figuring collision sets (moving vs. stationary) is helpful, but will not bring you far. If you implement a general NxM solution that is efficient you may actually get more bang for your buck. For starters you should separate your collision detection from your collision response. This makes sense since you may want to collide ...

0

An Elo-type system is designed to reflect a game where the #1 person is not expected to win every single match. A #1 ranked chess player might only beat the #10 ranked player 8 out of 10 times. The #1 ranked player is still better than the #10 ranked player but if you happen to observe only one of the 2 in 10 that the #10 ranked player won you wouldn't know ...

3

Always start with a triangle list... it's most general and easiest to think about. You'll end up with four categories of faces: cube faces (quad = 2 triangles each) edge bevels (quads = 2 triangles each) corner bevels (quads = 2 triangles each) corner tips (last triangle) There's different numbers of each of these, so they'll probably be handled ...

0

You can store the direction with 2 bits: 1 for axis and 1 for pos/neg. As such, storage-wise it will be more efficient regardless of the number of bends -- about ~2.5 KB for 10,000 tiles. Store it as a bitmask as well (1.25 KB for 10K tiles) and then you have fast collision checks ("is snake on tile"). The slowest operation would be "Access nth body part" ...

0

In the worst case it looks to me like you're going to use more memory this way. Picture a snake that goes something like this: ‾|_|‾|_|‾ as much as possible. There are a few spots at the edge of the screen where it must go straight for a few squares but those aren't enough to overcome the higher memory storage per location unless the world is small. While ...

0

One simple method is to use a force-directed graph approach. You model each vertex as a point mass in UV space. Each vertex receives a spring-like force that tries to keep it at the correct distance in UV space from each (post-seam-split) vertex with which it shares an edge, attractive when they're too far apart and repulsive when they're too close. That ...

Top 50 recent answers are included