Comments (5)
Hey cclog, Thanks for this. I think its a great idea to implement it like something like this. Its gonna take me a few weeks to get back to this issue (very busy weeks here, I'm helping with the organisation of a conference). So I wanted to add this comment here to show its not forgotten :).
from astar.
Hey Doug,
Great to hear that you're using the library. I think this is a good feature to add. I think the logic will be quite different than from the normal A* path finding so I will have to think about the implementation. But we can probably do something with keeping track of the path that got the closest 'as the crow flies' distance to the desired location. But there is a problem:
At the moment there is no distinction between a path blocked by an immovable object, or by an object that might move out of the way. So we could end up with a path that leads to a wall, meaning the agent will get near the object it desires to be, but even after fighting cannot reach it.
It would be great to hear from you if this limitation would still make the feature useful to you, or not.
from astar.
Posting this here instead of on #14
The general idea of 'best' path, from what I can tell, is taking the node that had the lowest H score in the case of no full path found. I just made some changes on my end to test this out and I think it works.
- In Grid.cs, "GetPath" becomes:
public Position[] GetPath(Position start, Position end, Offset[] movementPattern, int iterationLimit, out bool fullPathNotFound)
{
var current = PathFinder.FindPath(this, start, end, movementPattern, iterationLimit, out fullPathNotFound);
[...]
}
- In Pathfinder.cs "FindPath" method becomes:
public static List<Position> FindPath(Grid grid, Position start, Position end, Offset[] movementPattern, int iterationLimit, out bool fullPathNotFound)
{
ClearStepList();
fullPathNotFound = false;
if (start == end)
{
return new List<Position> { start };
}
var head = new MinHeapNode(start, ManhattanDistance(start, end));
MinHeapNode lowestHNode = head;
var open = new MinHeap();
open.Push(head);
var costSoFar = new float[grid.DimX * grid.DimY];
var cameFrom = new Position[grid.DimX * grid.DimY];
while (open.HasNext() && iterationLimit > 0)
{
// Get the best candidate
var currentNode = open.Pop();
var current = currentNode.Position;
MessageCurrent(current, PartiallyReconstructPath(grid, start, current, cameFrom));
if (currentNode.ExpectedCost < lowestHNode.ExpectedCost)
lowestHNode = currentNode;
if (current == end)
{
return ReconstructPath(grid, start, end, cameFrom);
}
Step(grid, open, cameFrom, costSoFar, movementPattern, current, end);
MessageClose(current);
--iterationLimit;
}
fullPathNotFound = true;
return ReconstructPath(grid, start, lowestHNode.Position, cameFrom);
//return null;
}
Also in my project, if the path kept coming back with "fullPathNotFound==true" (ie 2 in a row), then I would tell the unit to do something else, since obviously it can't make it to whatever it is trying to.
from astar.
I've thought about this more and more and I think every game has a different idea of "shortest to closest point", like what the closest point is (a closed door 10 meters away or an impenetrable wall 1 meter from the objective). For open areas that are congested with enemies its more clear. So I'm still not entirely sure what to do with this.
Maybe I can come up with an idea on how to give developers the tools to measure different types of closest points, and then let them plot a path there?
from astar.
Hi Roy,
This is an interesting idea. However, perhaps it would be best to hear from other users of your library to discern whether and how they might prefer this, rather than just taking one person's opinion.
I "solved" the problem "for now" by making nothing "impassible" (infinite value) but making game-impassible things very high path cost (like closed doors, other mobile objects) and letting the pathing algo do its thing and then not allowing the path to be followed at the appropriate point.
Cheers!
from astar.
Related Issues (20)
- Index was outside the bounds of the array error HOT 2
- Memory allocation number is unacceptable and library author ignoring the concerns HOT 5
- Considering the size of the agent
- Finding closest path to unreachable end cell HOT 4
- Deterministic? HOT 2
- Info: v2 WIP version available on Master HOT 2
- Hidden Connect method HOT 3
- Documentation / IntelliSense support HOT 5
- Isometric Support HOT 1
- Coming to v3 HOT 3
- Path. HOT 3
- No issue just a question. HOT 3
- Saving and loading graphs HOT 7
- TODO: release new minor version with save/load changes HOT 1
- just question HOT 2
- Question: GPS coordinates HOT 3
- Question HOT 1
- Explanation on how velocity is used HOT 6
- Question : Bidirectional graph search HOT 1
- Question: obstacles HOT 3
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from astar.