Tag Info

Hot answers tagged

12

There's a number of pieces to this puzzle, each of which will provide a deep and interesting rabbit hole of exploration. Some of them are: Level of Detail -- automatically (or "manually") choosing detailed or simplified models, or even sprites or just dots, or for objects as they are further away. Culling -- choosing to only draw what's needed. This might ...


11

What you want is to produce a dual graph; that is, a graph produced by converting faces to vertices, and connecting them based on adjacent faces in the original graph. Example: The problem, as you can see, is that if you want to keep the same layout of the graph, you'll get some really curvy edges in the dual graph. Also, you'll often end up with a ...


7

This is based on my speculation and skimming through Celestia's source code. Celestia allows you to fly around a planet and zoom out to see the whole galaxy. I browsed its source code and found it used an octree, a structure to recursively divide space into 8 octants. The renderer would render the environment by traversing the octree, and don't traverse ...


4

I would recommend an alternative approach: the rapidly exploring random tree (RRT). One cool thing about it is you can get it to go around corners, or explode in all directions. The algorithm is really basic: // Returns a random tree containing the start and the goal. // Grows the tree for a maximum number of iterations. Tree RRT(Node start, Node goal, int ...


3

Take a look at hierarchical A* (aka HPA*); its basically what you're looking for. However, keep in mind that adding pre-processing can add so much overhead that it might not be worth it. You will want to profile your existing planner first to make sure there aren't any obvious bottlenecks. Another thing you can try is to create a sparse probabalistic road ...


3

If vector (x,y) is a tangent vector of your curve, then the normal vector is simply (y,-x). So you just need to find a tangent vector, and it all depends on how exactly you define the curve. If your curve comes from a parametric representation p(t) = (x(t),y(t)) which is sufficiently continuous, then a good approximation of the tangent vector at t is, given ...


3

This is called the Pallet Loading Problem. Solving it is actually pretty hard, and we don’t know of an exact solution that always works in reasonable time. And sometimes the solution is not intuitive at all, see for instance: Here is a comprehensive list of existing algorithms (Recursive Five-block Algorithm, L-Algorithm, Recursive Partitioning ...


2

A hard but probably better way: if you walk on surfaces you would use navigation mesh based on triangles that share edges. In 3D space you could use tetrahedrons that share faces. Tetrahedrons should be able to fill your space reasonably and running A* on the graph of tetrahedra should be much faster, as you would probably not need so many of them. As in ...


2

You're on the right track. However... Try O(n*m) runtime is typical with something like this. Your implementation is a bit excessive, however. The real question is, What is making your O(n*m) algorithm take so long? Why bother to run through every map cell for each influence? It would be faster to have each starting influence also specify some random ...


2

I recently encountered a related problem to do with packing a texture atlas. The main difference for yours is that you prefer "closest to a target point" result. But I think the approach will work about the same... All of the candidate locations for the new rectangle have the following property: One of its corners will lie on one of the "implied grid ...


2

Anything that is either hierarchical and/or sparse should help you out here. There's a lot of empty space, so not having to use storage to represent empty space is a must. A typical hierarchical approach would be something like an Oct tree which recursively subdivides space into 8 smaller cubes, and you can store objects in the smallest cube that they can ...


1

If the first image, where each point is a small square with certain color, is what you are searching for, you need to build the Delaunay's triangulation.


1

Instead of iterating over all plates, consider only those empty cells that could possibly be filled: namely those that are adjacent to at least one already filled cell. Your algorithm could then become something like this: 1) Keep track of all unfilled cells that have at least one adjacent filled cell. 2) Select one of these unfilled cells. 3) Select one ...


1

Given that top left is at 0, and each tile is square with length 10: int squareClickedX = clickPosX / 10 int squareClickedY = clickPosY / 10 So, if clicked on x23, y12 int squareClickedX = 23 / 10 int squareClickedY = 12 / 10 results int squareClickedX = 2 int squareClickedY = 1 Means that you clicked Was this any good? This is quite common way ...


1

The question is, what pattern you want to achieve, and how to randomize the given pattern. You could place fix walls in a grid shape, then fill the rest with walls, and when you place the players, clear enough space for them to start. Then you could start randomizing things: Player starting position. Don't forget to check if the players aren't too close. ...


1

Keep in mind that this algorithm is for zero-sum games, where the game state is known by all parties involved. The numbers given are those calculated by an evaluation function ran on the game state after x number of turns; for instance, in Tic Tac Toe, after a certain amount of turns, you know whether you won (+infinity), your opponent won (-infinity) or ...


1

You can think of the numbers as "relative advantage to the Max player" Max wants to maximize their advantage relative to Min. Min wants to maximize their advantage relative to Max, which is equivalent to minimizing Max's advantage over them. Relative advantage could be computed as something like a score gap (if Max has 2 points to Min's 3, that means Max ...



Only top voted, non community-wiki answers of a minimum length are eligible