Tag Info

New answers tagged

2

There is really nice article at Rogue Basin on Dijkstra Maps about the problem you are encountering. This kind of "exploit" can be easily overused, cornering range units, while they are try to flee, they really stuck and can't move away. The article describes making "negative" Dijkstra maps. You create normal Dijkstra map, multiply result by value -1.2, and ...


5

First think of what you would do as a player (and/or ask others what they would do) and then try to program one or more of those strategies. There are probably several situations where a simple rule won't be a good idea to follow. This is actually a good thing, because otherwise your game would be fairly pointless to play as a human. Having an AI that can ...


2

Clustering in Graphs I'm not sure why your assignment has given you an open research problem (clustering in graphs) to solve. Please ask your professor if this is really required before continuing. If you know the number of clusters, (or can guess them) I would suggest trying something like spectral clustering, or K-means clustering; using the number of ...


8

Yes, navigation meshes are still applicable to tile based games. Although, they would primarily be used as a optimization. For example, I've converted the lower left of your image to use a navigation mesh: In this case, each green square would be a navigation node. As you can see, this drastically reduces the number of nodes that A* needs to process. ...


2

Breadth First Search can calculate every location reachable from a start position, and it can also count how many steps to that location. (If some steps take more "moves" then use Dijkstra's Algorithm instead). See the fourth demo on this page. You would tell the algorithm to stop after some number of moves, so that it doesn't keep exploring the rest of the ...


2

std::vector< std::vector<Node> > mNodes_(257, std::vector<Node>(257, Node(sf::Vector2i(0, 0)))); This isn't optimal, a more efficient structure would be a std::vector<Node> mNodes_(257*257, Node(sf::Vector2i(0, 0))); and index with x*257 + y. You can possibly keep it allocated statically (or thread locally when multithreading) ...


0

Another possible optimization would be to not use priority_queue... Using priority queue won't let you update each node distance individually (which is needed for A*). Using a custom implementation of min-heap, you can fix that issue. This way pushing, and popping nodes into the heap would be of O(logn), and so will updating be. But size of your heap will ...


3

Rather than pre-calculating every distance, simply pre-calculate the distances to and from each corner of the map to every node(perfect use-case for Dijkstra's algorithm) and then use this information and the Triangle inequality to generate a heuristic. This algorithm modification is referred to as ALT, or A-star with Landmarks and Triangle inequality. I ...


3

Welcome to the wonderful world of continuous state motion planning. A few years ago I wrote a Gamasutra article on this topic. Here are some solutions to your problem: Navigation Meshes This works by constructing a graph of nodes and edges of your scene based on some simple rules. For instance, you can construct a Visibility Graph of the scene, which is ...


1

Simple, give the monster a hspeed, vspeed speed components, after that find the direction to the next point in the path with the tangent, which if I recall correctly would be y2-y1/x2-x1, being x2 and y2 the point of the next position and x1 and y1 the monster one. After that use the cosinespeed to find the x component or hspeed and -sinespeed for the y ...


1

If you implemented A* correctly then you would have a "open" list of nodes to search sorted by the expected cost of a path through that node or d(start, node)+h(node, end) This means that the 2,0 node should still be in the list. But The algorithm should continue with 3,3. If it doesn't then the way you select the next node to investigate is flawed.


0

As long as there are no overlapping walkable areas, you can keep 2D A*. You just need to add a height info to tiles and make a rule, that character can walk from tile to tile if height difference is less than X. If there are overlapping areas you need to go kind of 3D. You can get away with several separate layers for your room, where each layer contains ...



Top 50 recent answers are included