Comments (7)
From the top of my head I can think of two approaches to make this more efficient:
A) In Terrain\MyAStar.php
a MyNode
object is created from a Node
object:
$myNode = MyNode::fromNode($node);
However, this is not necessary, as the $node object is actually a MyNode
.
B) Use a cache of nodes. Before creating a new node, check if that node already exists in the cache. If so, return the existing one.
Both changes would happen at the Example level, rather than at the Algorithm level. When I created the examples, I focused more on making them easy to understand, rather than on efficiency, because the point of the examples is that a new user can understand how to use the algorithm. That's why I'm not inclined to sacrifice clarity for efficiency in the examples.
However, I think that option B can be used at the algorithm level after the changes in #9 have been developed, because in that case the user won't be creating a full node anymore, the nodes will be handled entirely by the algorithm, and I am more than happy to make the algorithm more efficient.
So, as a summary, this is what I expect from each part of the code:
- examples folder: easy to understand.
- src folder (actual algorithm): efficiency.
I think we should keep this issue open and try to implement a node cache after #9 has been developed.
And, of course, I'm open to discuss any suggestions you may have.
Thanks once again for your feedback, I really appreciate it.
from php-a-star.
That makes sense.
I was wondering about your intent with the code. An optimized version could be very ugly for learning.
from php-a-star.
Related to this, if you keep the nodes around, then you can store useful data in them.
That can have multiple benefits including reducing the need for new calls.
For example in this code, instead of keeping a Closed list, there is just a "closed" flag on each node: https://github.com/pathway/go-astar/blob/master/astar.go
from php-a-star.
Thanks for the link, it's very interesting. I see that it also has a flag on every node to check if it belongs to the open list as well, it's a very clever implementation.
Once #9 has been implemented and the user has no access to the nodes, we can try to implement that. I think the highest priority right now should be to create the benchmark utility. Once that's done it will help us greatly to test the performance of new features against the current ones.
from php-a-star.
The flags on nodes are not uncommon so I dont feel you would be taking a unique design if you did that.
And I think your idea of benchmark reading/writing terrain files makes a lot more sense than my approach of pasting massive arrays into source code. It was just faster to get started so we could see numbers asap =D
from php-a-star.
Don't worry, I understand why you did it like that, and it was very helpful :)
from php-a-star.
Update after the v2.0.0 release:
At the moment, we create a new Node
object per neighbour every time we make a call to AStar::generateAdjacentNodes
, even when we have already created the same neighbour in previous calls to this function. As discussed in previous comments, a cache of nodes could help mitigate this.
The cache should implement the PSR-16 standard. We will need to add a new composer dependency: psr/simple-cache
, as well as another dependency for its implementation.
One possible way to implement this would be to create a Score
object (with the f
, g
and h
properties). Each Node
object will have two Score
objects: the normal and tentative scores. When we call getAdjacentNodesWithTentativeScore
, it will return the nodes that we have actually processed and stored in the cache (except for the ones we haven't created them yet, in which case we create the new ones and store them in the cache), and it will populate the tentative score, rather than the actual score. In fact, instead of calling getAdjacentNodesWithTentativeScore
in the main loop, we can call two methods: one of them to get the successors (it will create new ones or return the existing ones from the cache), and then we call a new method: calculateTentativeScore
.
The Node
object could also have a new acceptTentativeScore(): void
method that we will call before adding the node to the open list, and that will copy the values of the tentative score to its actual score.
The Node
object won't need to expose the whole tentative score object, since we will only need to set and retrieve its G score. Perhaps this means that creating a new Score
object could be overkill, an a simple float | int $tentativeG
could be enough.
from php-a-star.
Related Issues (13)
- Create a benchmark utility HOT 1
- Maybe consider generalizing the algorithm to allow for BFS, UCS, DFS, etc HOT 2
- Measure memory usage in the benchmark
- Measure number of nodes expanded in the benchmark
- Run static analysis tools HOT 1
- Exclude unnecessary files when composer is run with --prefer-dist
- Parent loop HOT 2
- Remove unneeded methods in the Node interface
- Improve the NodeList's efficiency HOT 4
- Scrutinizer support
- Enforce the coding standards via Travis-CI HOT 1
- Ease the library usage HOT 2
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 php-a-star.