daancode / a-star Goto Github PK

View Code? Open in Web Editor NEW

443.0 9.0 121.0 7 KB

A* algorithm C++ implementation.

License: MIT License

C++ 96.69% CMake 3.31%

a-star's People

Contributors

Stargazers

Watchers

Forkers

rgeorgiev583 bugttle nnbinh1987 kamikoto66 jimaldon pulsartao praveenmunagapati dongbu iwatakeshi raihantusher hanbim520 dorimu moscatomao megasprite byfron ryzejiang vectorer marxss ryouyg c722996 leguims facontidavide panecho paulestano meng216073 ossease ysonggit francis65916 cthlinmeng firedtoad debruw jiang-jiaxin arthurluchina bigbugisme sdgmch liuqj raychenv haohan1997 wxbbuaa2011 maidoufu mtau87 penghao1023 leibinhua sadchinav kingwoshi gongkaka ovionet changyuke fullchen hang-cs omar-alghanmi jaffrykee ssj65 sryanyuan sabrefoxx ccylovemm yangchao-0 anki-0 tomatochewgum knu-software-algorithms ohhandsome dehucoh workshoft wanbaocheng sfzheng7 gambetaclub sdraeger mu-l liujiang98 ttomchy darkxex supremezyh gamedevcpp idiosun mysticouo straycat2486 timsu-98 lightraing 0xdddddddd jjinglover naleraphael yangxingbang sim15 shenweihuaa vfrancescon 6guoqiang6 donneylucks zph517 zhenya-lei harry0217chua weiwen1990 rv4src eclipse1984 vbirds dealbreaker351 bo-hui ricardobin1 peerlesszhu elh4m 14chanwa

a-star's Issues

contributor information

Hi Daan

I am A student who benefits from your work, because your open source A-Star algorithm in Github makes my experiment easier. I used your open source code in my paper, but I cannot get further information about you, so I write this email specially, hoping that you can provide the university or company where you study or work and the name of the author if it is convenient for you. In order to be able to quote your work and express thanks to you in my paper.

thanks

目测你的算法只是实现了功能，效率一般

What framework is used to visualize the algorithm results

Ask a question，What framework is used to visualize the algorithm results.

if there is no path, this algorithm cost so much time and give a wrong path

Code seems to be executing endlessly, causing the thread to hang

I'm running this code to periodically find path for ~20000 entities in several maps. The code can be found here - https://github.com/horizonxyz/horizon/blob/status/src/Server/Zone/Game/Map/Path/AStar.hpp

Just to provide a better understanding of how my code works -
move_to_coordinates() -> https://github.com/horizonxyz/horizon/blob/status/src/Server/Zone/Game/Map/Path/AStar.hpp
path finding -> https://github.com/horizonxyz/horizon/blob/status/src/Server/Zone/Game/Entities/Entity.cpp#L82

The code seems to hang the thread and executes endlessly, making it very hard to debug. Maybe it hasn't found the path or is continuously finding it for one of the entities. I can't put my finger on it but was hoping that someone might be able to point out the cause.

Stack trace showing where it continuously computes and hangs the thread, but doesn't crash. -

  thread #2
    frame #0: 0x00000001005db0cb zone`bool std::__1::operator==<Horizon::Zone::AStar::Node**, Horizon::Zone::AStar::Node**>(__x=0x0000700004fd2ae0, __y=0x0000700004fd2ad8) at iterator:1527:5
    frame #1: 0x00000001005d96cd zone`bool std::__1::operator!=<Horizon::Zone::AStar::Node**>(__x=0x0000700004fd2ae0, __y=0x0000700004fd2ad8) at iterator:1579:18
    frame #2: 0x00000001005d9a1f zone`Horizon::Zone::AStar::Generator::findNodeOnList(this=0x00000000140db760, nodes_=<unavailable>, coordinates_=(x = 79, y = 239, move_cost = 0)) at AStar.hpp:109:18
    frame #3: 0x00000001005d2dc3 zone`Horizon::Zone::AStar::Generator::findPath(this=0x00000000140db760, source_=(x = 131, y = 242, move_cost = 0), target_=(x = 136, y = 245, move_cost = 0)) at AStar.hpp:185:9
    frame #4: 0x00000001005d2274 zone`Horizon::Zone::Entity::schedule_movement(this=0x0000000007f7a800, coords=(_x = 136, _y = 245))416>) at Entity.cpp:82:38
    frame #5: 0x00000001005d3abf zone`Horizon::Zone::Entity::move_to_coordinates(this=0x0000000007f7a800, x=136, y=245) at Entity.cpp:157:2
    frame #6: 0x0000000100600b02 zone`Horizon::Zone::Entities::Monster::initialize(this=0x0000000007f7b268, context=TaskContext @ 0x0000700004fd32d0)::$_0::operator()(TaskContext) const at Monster.cpp:61:3
    frame #7: 0x0000000100600986 zone`decltype(__f=0x0000000007f7b268, __args=0x0000700004fd3438)::$_0&>(fp)(std::__1::forward<TaskContext>(fp0))) std::__1::__invoke<Horizon::Zone::Entities::Monster::initialize()::$_0&, TaskContext>(Horizon::Zone::Entities::Monster::initialize()::$_0&, TaskContext&&) at type_traits:4361:1
    frame #8: 0x0000000100600912 zone`void std::__1::__invoke_void_return_wrapper<void>::__call<Horizon::Zone::Entities::Monster::initialize(__args=0x0000000007f7b268, __args=0x0000700004fd3438)::$_0&, TaskContext>(Horizon::Zone::Entities::Monster::initialize()::$_0&, TaskContext&&) at __functional_base:349:9
    frame #9: 0x00000001006008c2 zone`std::__1::__function::__alloc_func<Horizon::Zone::Entities::Monster::initialize()::$_0, std::__1::allocator<Horizon::Zone::Entities::Monster::initialize()::$_0>, void (TaskContext)>::operator(this=0x0000000007f7b268, __arg=0x0000700004fd3438)(TaskContext&&) at functional:1527:16
    frame #10: 0x00000001005ff5d1 zone`std::__1::__function::__func<Horizon::Zone::Entities::Monster::initialize()::$_0, std::__1::allocator<Horizon::Zone::Entities::Monster::initialize()::$_0>, void (TaskContext)>::operator(this=0x0000000007f7b260, __arg=0x0000700004fd3438)(TaskContext&&) at functional:1651:12
    frame #11: 0x00000001005b6115 zone`std::__1::__function::__value_func<void (TaskContext)>::operator(this=0x0000000007f7b260, __args=0x0000700004fd3438)(TaskContext&&) const at functional:1799:16
    frame #12: 0x00000001005a0428 zone`std::__1::function<void (TaskContext)>::operator(this=0x0000000007f7b260, __arg=<unavailable>)(TaskContext) const at functional:2347:12
    frame #13: 0x000000010059f12f zone`TaskContext::Invoke(this=0x0000700004fd34e0) at TaskScheduler.cpp:246:2
    frame #14: 0x000000010059e656 zone`TaskScheduler::Dispatch(this=0x0000000007f7a840, callback=0x0000700004fd35a0)> const&) at TaskScheduler.cpp:105:11
    frame #15: 0x000000010059e4ca zone`TaskScheduler::Update(this=0x0000000007f7a840, callback=0x0000700004fd35a0)> const&) at TaskScheduler.cpp:28:2
    frame #16: 0x00000001005d3b2e zone`Horizon::Zone::Entity::update(this=0x0000000007f7a800, diff=1614191228) at Entity.cpp:164:13
    frame #17: 0x00000001006de232 zone`Horizon::Zone::MapContainerThread::start_internal(this=0x000000000d621ec8, context=TaskContext @ 0x0000700004fd3850)::$_0::operator()(TaskContext) const at MapContainerThread.cpp:180:13
    frame #18: 0x00000001006de0a6 zone`decltype(__f=0x000000000d621ec8, __args=0x0000700004fd39b8)::$_0&>(fp)(std::__1::forward<TaskContext>(fp0))) std::__1::__invoke<Horizon::Zone::MapContainerThread::start_internal()::$_0&, TaskContext>(Horizon::Zone::MapContainerThread::start_internal()::$_0&, TaskContext&&) at type_traits:4361:1
    frame #19: 0x00000001006de032 zone`void std::__1::__invoke_void_return_wrapper<void>::__call<Horizon::Zone::MapContainerThread::start_internal(__args=0x000000000d621ec8, __args=0x0000700004fd39b8)::$_0&, TaskContext>(Horizon::Zone::MapContainerThread::start_internal()::$_0&, TaskContext&&) at __functional_base:349:9
    frame #20: 0x00000001006ddfe2 zone`std::__1::__function::__alloc_func<Horizon::Zone::MapContainerThread::start_internal()::$_0, std::__1::allocator<Horizon::Zone::MapContainerThread::start_internal()::$_0>, void (TaskContext)>::operator(this=0x000000000d621ec8, __arg=0x0000700004fd39b8)(TaskContext&&) at functional:1527:16
    frame #21: 0x00000001006dccf1 zone`std::__1::__function::__func<Horizon::Zone::MapContainerThread::start_internal()::$_0, std::__1::allocator<Horizon::Zone::MapContainerThread::start_internal()::$_0>, void (TaskContext)>::operator(this=0x000000000d621ec0, __arg=0x0000700004fd39b8)(TaskContext&&) at functional:1651:12
    frame #22: 0x00000001005b6115 zone`std::__1::__function::__value_func<void (TaskContext)>::operator(this=0x000000000d621ec0, __args=0x0000700004fd39b8)(TaskContext&&) const at functional:1799:16
    frame #23: 0x00000001005a0428 zone`std::__1::function<void (TaskContext)>::operator(this=0x000000000d621ec0, __arg=<unavailable>)(TaskContext) const at functional:2347:12
    frame #24: 0x000000010059f12f zone`TaskContext::Invoke(this=0x0000700004fd3a60) at TaskScheduler.cpp:246:2
    frame #25: 0x000000010059e656 zone`TaskScheduler::Dispatch(this=0x00000000031028b0, callback=0x0000700004fd3d20)> const&) at TaskScheduler.cpp:105:11
    frame #26: 0x000000010059e4ca zone`TaskScheduler::Update(this=0x00000000031028b0, callback=0x0000700004fd3d20)> const&) at TaskScheduler.cpp:28:2
    frame #27: 0x00000001006c8ca9 zone`Horizon::Zone::MapContainerThread::update(this=0x00000000031027b0, diff=1614191215) at MapContainerThread.cpp:245:17
    frame #28: 0x00000001006c7f5b zone`Horizon::Zone::MapContainerThread::start_internal(this=0x00000000031027b0) at MapContainerThread.cpp:187:3
    frame #29: 0x00000001006d9f51 zone`decltype(__f=0x00000000030124c8, __a0=0x00000000030124d8)).*fp()) std::__1::__invoke<void (Horizon::Zone::MapContainerThread::*)(), Horizon::Zone::MapContainerThread*, void>(void (Horizon::Zone::MapContainerThread::*&&)(), Horizon::Zone::MapContainerThread*&&) at type_traits:4302:1
    frame #30: 0x00000001006d9e5e zone`void std::__1::__thread_execute<std::__1::unique_ptr<std::__1::__thread_struct, std::__1::default_delete<std::__1::__thread_struct> >, void (Horizon::Zone::MapContainerThread::*)(), Horizon::Zone::MapContainerThread*, 2ul>(__t=size=3, (null)=__tuple_indices<2> @ 0x0000700004fd3eb8)(), Horizon::Zone::MapContainerThread*>&, std::__1::__tuple_indices<2ul>) at thread:342:5
    frame #31: 0x00000001006d9686 zone`void* std::__1::__thread_proxy<std::__1::tuple<std::__1::unique_ptr<std::__1::__thread_struct, std::__1::default_delete<std::__1::__thread_struct> >, void (Horizon::Zone::MapContainerThread::*)(), Horizon::Zone::MapContainerThread*> >(__vp=0x00000000030124c0) at thread:352:5
    frame #32: 0x00007fff78ddf2eb libsystem_pthread.dylib`_pthread_body + 126
    frame #33: 0x00007fff78de2249 libsystem_pthread.dylib`_pthread_start + 66
    frame #34: 0x00007fff78dde40d libsystem_pthread.dylib`thread_start + 13

E: Package g++-4.8 has no installation candidates

sudo apt-get install -qq g++-4.8
E: Package g++-4.8 has no installation candidates

Can we use your code as MIT or LGPL ?

Hi,

We would like to use your code as either MIT or LPGL. Would that be ok for you ? We do need a fast answer though...

Thanks !

no gui output

g@g:/A_star/a-star$ ./app
Generate path ...
20 20
19 19
18 18
17 17
16 16
15 15
14 14
13 13
12 12
11 11
10 10
9 9
8 8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
0 0
g@g:/A_star/a-star$

No documentation and protection on 'Vec2i' initialisation

Hi,

Your repo is really useful, and a use it to do a Quoridor board game. When I try to use a-star, I find no documentation to know the relative limits to setWorldSize() method.

Now, I know, but it could be usefull to add this information in 'ReadMe.md' or in 'AStar.hpp'. Best fix is to add exception if 'Vec2i' when coordinates is out of range (std::out_of_range for example).

World = [ 0 ; WorldSize - 1 ]
All 'Vec2i.x' and 'Vec2i.y' have to be in [0 ; WorldSize - 1].

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.