Tag Info

New answers tagged

0

You could use a heuristic function that given a score and a prediction calculates the "value" of the prediction as an integer. This "value" could be the distance between the prediction and the score (a negative value means the prediction is impossible, 0 means it's an exact match and a positive value means it's still possible). Since the "value" of each ...


0

With rect_coordinate ranging from -1 to 1 and assuming sin/cos functions take radian as inputs, for each pixel in the rectangular texture do: color CubeToRectangle(vec2 rect_coordinate) { vec3 cube_map_coordinate; cube_map_coordinate.x = cos(rect_coordinate.x * PI * 2) * cos(rect_coordinate.y * PI); cube_map_coordinate.y = sin(rect_coordinate.y ...


0

You can compare the polygon surface to the surface at the end of its normals (or a small factor of) Calculating it with a normal map is similar. iterate over the polygon using the normal map's texels.


0

This is rather problem to sum numbers between n and m, which is pretty widely known: it is sum of numbers 1 to m minus sum of numbers 1 to n(n-1 infact, but it gets eliminated in the code) plus x, ofcourse. In your example, it is: index = columnCount * ( columnCount + 1 ) / 2 - ( columnCount - y ) * ( columnCount - y + 1 ) / 2 ) + x; plus, since column ...


0

If you're looking for a single heat value you can calculate the distance between your sample point and all sources & sinks in a straight line. If there is a wall in a straight line, calculate from your sample to the ends of the wall and then to the source/sink. it gets a bit more complicated with walls made of multiple segments due to being potentially ...


1

One distance field cannot represent sharp corners, because within the space between 4 samples (i.e. inside each "square pixel", even though pixels are not little squares), the value of the distance field is a quadratic function due to bi-linear interpolation. This class of quadratics cannot represent sharp corners well, because they are polynomials and ...


0

Your normals are supposed to be the face normals of a polygon. If your vertices are an oriented array in counter clockwise order, then you can easily compute the normal of a face by a 90 degree rotation. So if we have an edge on a polygon made of the vertices a and b, we know that the edge is oriented from a to b going around the polygon in CCW order. To ...


0

Here is my java implementation to get the closest one from a quadTree. It deals with the problem dlras2 is describing: I think the operation is really efficient. It is based on the distance to a quad to avoid searching in quads further way then the current closest. // . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ...


0

If you know the shape of the piece, and you know where you want to place it, I would assume you have determined the orientation of the piece already. If this is the case then I think the solution is fairly straight forward. You have a default orientation for each piece, and depending on the piece 0-3 possible alternate orientations. The number of rotations ...


4

I added another answer for an alternative explanation of the problem. You can think of this problem as Motion Planning in the Configuration Space of the tetris piece. The Configuration Space Define the configuration of a Tetris piece to be an (x, y) location and a rotation (t). The configuration of a Tetris piece is therefore three dimensional. We can ...


2

I am assuming that your problem is: Assume the placement location is known. How do I find the optimal sequence of moves to put the piece in the correct location? One answer to this question is to interpret the problem as an Action Planning problem. The simplest algorithm to solve it is probably STRIPS. There is another algorithm that is a more ...


1

To calculate perspective projection divide by w. vec4 result = vec4(x, y, z, 1) * perspective_view_model_matrix; result /= w; You are then left with the (x,y) in screen space (-1 to 1). Multiply this by 1/2 screen width,height and you get pixel coordinates. You then need to take the corresponding vertex UVs, multiply by the texture size and you get ...


0

when I click an impassable tile, the algorithm apparently goes through the entire map to find a route to the impassable tile — even if I'm standing next to it. Other answers are great, but I have to point at the obvious - You should not run the pathfinding to an impassable tile at all. This should be an early exit from the algo: if not IsPassable(A) ...


0

If the areas that the player are connected (no teleports etc.) and the unreachable areas are generally not very well connected, you can simply do the A* starting from the node you want to reach. That way you can still find any possible route to the destination and A* will stop searching quickly for unreachable areas.


0

To check for the longest distance in a graph between two nodes: (assuming all edges have the same weight) Run BFS from any vertex v. Use the results to select a vertex furthest away from v, we'll call it d. Run BFS from u. Find the vertex furthest away from u,we'll call it w. The distance between u and w is the longest distance in the graph. Proof: ...


5

Here's a vector-based solution. I haven't tried it, but it seems fine conceptually. Theory I gather you've stored the shape as line segments. Here's the letter A represented with three line segments. I've assumed that paths in the user's drawing are stored as lists of points. We can "inflate" those line segments to allow an error margin when checking ...


3

Use multiple algorithms with different characteristics A* has some fine characteristics. In particular, it always finds the shortest path, if one exist. Unfortunately, you have found some bad characteristics as well. In this case, it must exhaustively search for all possible paths before admitting no solution exists. The "flaw" you are discovering in A* ...


0

The best solution not use graphics at all, do it with math! You can easy understand how much every point (user painted) far from segment http://stackoverflow.com/questions/849211/shortest-distance-between-a-point-and-a-line-segment That you can calculate average error, so measure how much user is correct.


0

tl;dr I suggest making the players' brush paint a visible (or invisible) 2d plane. Diff the users' painted image with the origin (the desired silhouette or 2d model). If you want to increase accuracy then make the guiding lines and brush more narrow, to allow more room for error, make brush and design thicker. Otherwise, you could measure the distance of ...


0

Do the path-finding backwards. If only your map doesn't have big continuous areas of unreachable tiles then this will work. Rather than searching the entire reachable map, the path-finding will only search the enclosed unreachable area.


11

Assuming the issue is the destination is unreachable. And that the navigation mesh isn't dynamic. The easiest way to do this is have a much sparser navigation graph (sparse enough that a full run through is relatively quick) and only use the detailed graph if the pathing is possible.


1

How can I make A* more quickly conclude that a node is impassable? Profile your Node.IsPassable() function, figure out the slowest parts, speed them up. When deciding whether a node is passable, put the most likely situations at the top, so that most of the time the function returns right away without bothering to check the more obscure possibilities. ...


2

Some more ideas in addition to the answers above: Cache results of A* search. Save the path data from cell A to cell B and reuse if possible. This is more applicable in static maps and you will have to do more work with dynamic maps. Cache the neighbours of each cell. A* implementation need to expand each node and add its neighbours to the open set to ...


1

If your map is static you can just have each separate section have there own code and check this first before running A*. This can be done upon map creation or even coded in the map. Impassable tiles should have a flag and when moving to a tile like that you could opt not to run A* or pick a tile next to it that is reachable. If you have dynamic maps ...


37

Some ideas on avoiding searches that result in failed paths altogether: Island ID One of the cheapest ways to effectively finish A* searches faster is to do no searches at all. If the areas are truly impassible by all agents, flood fill each area with a unique Island ID on load (or in the pipeline). When pathfinding check if the Island ID of the origin of ...


17

Run a dual A* search from the target node in reverse as well at the same time in the same loop and abort both searches as soon as one is found unsolvable If the target has only 6 tiles accessible around it and the origin has 1002 tiles accessible the search will stop at 6 (dual) iterations. As soon as one search finds the other's visited nodes you can ...


24

AStar is a complete planning algorithm, meaning if there exists a path to the node, AStar is guaranteed to find it. Consequently, it must check every path out of the start node before it can decide the goal node is unreachable. This is very undesirable when you have too many nodes. Ways to mitigate this: If you know a priori that a node is unreachable ...


0

One way to do it with puzzle games is to start from the end and create the level in reverse. This has the added bonus that all your puzzles are guaranteed solvable. Finding the absolute minimum number of steps might be good for a university paper but you don't need to find it for a good game. Players love finding better ways to solve the puzzle. The ego ...



Top 50 recent answers are included