Tag Info

New answers tagged

0

Since you mention voronoi, i'll give my c# voronoi implementation private void Voronoi(int[,] points, int minDelta) { for (int i = 0; i < wid; i++) { for (int j = 0; j < hei; j++) { float minDist = 999999999f; float minDist2 = 999999999f; float minV = 0f; for (int p = 0; p < ...


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 ...


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 ...


0

You could try doing things in reverse. Start with an empty grid and place the boundary walls on the play field. Then define a bunch of wall patterns that you can choose from. ... ie a straight section, an L shape, a C shape etc. Randomly place these on the map testing to make sure you still have a valid map. ie One that is not completely closed off by ...


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 ...


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 ...


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 ...


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 ...


0

Here is my working AStar implementation built in Java on the LibGdx framework (it should not be too difficult to adapt to C#): public class AStar { /** * Makes the end passable, if it wasn't already, and then finds the shortest path towards it, using the AStar algorithm. * @param start The node to start the search from. * @param end The ...


0

There are a lot of resources on the web for understanding alpha-beta. This short video will probably help you understand: https://www.youtube.com/watch?v=xBXHtz4Gbdo My 1st game was an alpha-beta Othello, back in 1981. Good luck! Footnote: once you get alpha-beta working, if you want to search deeper, I recommend the "MTD(f)" algorithm with "Iterative ...


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 ...


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 ...


1

(A place to start that's easier than comments:) Maintain a list of tiles that need calculating; the initial list contains only the city-tiles. Each city-tile generates influence, X, and adds it to each of its' 8 nearest neighbors, also adding each neighbor to the list. (Does the city pass only 1/8 of its influence to each?) The city-tile then removes ...



Top 50 recent answers are included