How to implement the A Star find path algorithm using NIF?

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

How to implement the A Star find path algorithm using NIF?

skyman-2
Hi everybody,

Our game is using A Star algorithm to find path. For performance I want to write it in C language, and Erlang calls it by NIF. I don't know whether the map data is maintained in C or in Erlang. Can anyone tell me?
In addition, is there any better solution than NIF?

Thanks very much!


 


_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: How to implement the A Star find path algorithm using NIF?

Dmitry Kolesnikov-2
Hello,

On 10 Jul 2017, at 19.11, skyman <[hidden email]> wrote:

Hi everybody,

Our game is using A Star algorithm to find path. For performance I want to write it in C language, and Erlang calls it by NIF. I don't know whether the map data is maintained in C or in Erlang. Can anyone tell me?

Map is native data structure. However, you need to use enif interface to interact with it. 

In addition, is there any better solution than NIF?

I’ve used to solve a “routing” issues on pure Erlang using ETS, lists, etc. However, this mainly depends on your traffic, latency and size of routing tables. It is hard to give a straight forward answer not knowing this figures.      



Thanks very much!

Best Regards, 
Dmitry

_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: How to implement the A Star find path algorithm using NIF?

skyman-2
Hi Dmitry,

Thanks for your reply.
The map of our game is large(1000 * 1000 grids). If I use NIF to implement the A Star find path in C, can I allocate the map grid array(1000 * 1000) in C, and when map blocks changed, Erlang calls 'updateBlock' NIF to update the grid state in grid array in C?

Thanks!




At 2017-07-11 00:33:34, "Dmitry Kolesnikov" <[hidden email]> wrote:
Hello,

On 10 Jul 2017, at 19.11, skyman <[hidden email]> wrote:

Hi everybody,

Our game is using A Star algorithm to find path. For performance I want to write it in C language, and Erlang calls it by NIF. I don't know whether the map data is maintained in C or in Erlang. Can anyone tell me?

Map is native data structure. However, you need to use enif interface to interact with it. 

In addition, is there any better solution than NIF?

I’ve used to solve a “routing” issues on pure Erlang using ETS, lists, etc. However, this mainly depends on your traffic, latency and size of routing tables. It is hard to give a straight forward answer not knowing this figures.      



Thanks very much!

Best Regards, 
Dmitry


 


_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: How to implement the A Star find path algorithm using NIF?

Dmitry Kolesnikov-2
Hello,

It looks you are trying to implement a hybrid solution a mix up of Erlang and C code for routing. Unless, I’ve not understood your question. I would either implement A* purely native or purely in Erlang. In both cases, I would target a data structure that best suites your problem and implementation techniques.   

Let’s say, you’ve made decision to implement A* in C then I would design a NIF API to address problem of A* search rather then memory management. In this case the updateBlock routine becomes internal for your C code.   

BTW, Have you consider to use Cpp and NIFpp wrapper for Erlang to integrate existed A* algorithms ?

Best Regards, 
Dmitry


On 10 Jul 2017, at 20.03, skyman <[hidden email]> wrote:

Hi Dmitry,

Thanks for your reply.
The map of our game is large(1000 * 1000 grids). If I use NIF to implement the A Star find path in C, can I allocate the map grid array(1000 * 1000) in C, and when map blocks changed, Erlang calls 'updateBlock' NIF to update the grid state in grid array in C?

Thanks!




At 2017-07-11 00:33:34, "Dmitry Kolesnikov" <[hidden email]> wrote:
Hello,

On 10 Jul 2017, at 19.11, skyman <[hidden email]> wrote:

Hi everybody,

Our game is using A Star algorithm to find path. For performance I want to write it in C language, and Erlang calls it by NIF. I don't know whether the map data is maintained in C or in Erlang. Can anyone tell me?

Map is native data structure. However, you need to use enif interface to interact with it. 

In addition, is there any better solution than NIF?

I’ve used to solve a “routing” issues on pure Erlang using ETS, lists, etc. However, this mainly depends on your traffic, latency and size of routing tables. It is hard to give a straight forward answer not knowing this figures.      



Thanks very much!

Best Regards, 
Dmitry


 


_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: How to implement the A Star find path algorithm using NIF?

Son Tran-Nguyen-3
Hello,

While the choice of C may not be changed, I would suggest writing your algorithm in Rust 
and use something like https://github.com/hansihe/rustler.

It's still NIF, but Rust will handle bad codes for you, making your NIF safe.

Just a thought.

On Mon, Jul 10, 2017 at 12:32 PM, Dmitry Kolesnikov <[hidden email]> wrote:
Hello,

It looks you are trying to implement a hybrid solution a mix up of Erlang and C code for routing. Unless, I’ve not understood your question. I would either implement A* purely native or purely in Erlang. In both cases, I would target a data structure that best suites your problem and implementation techniques.   

Let’s say, you’ve made decision to implement A* in C then I would design a NIF API to address problem of A* search rather then memory management. In this case the updateBlock routine becomes internal for your C code.   

BTW, Have you consider to use Cpp and NIFpp wrapper for Erlang to integrate existed A* algorithms ?

Best Regards, 
Dmitry


On 10 Jul 2017, at 20.03, skyman <[hidden email]> wrote:

Hi Dmitry,

Thanks for your reply.
The map of our game is large(1000 * 1000 grids). If I use NIF to implement the A Star find path in C, can I allocate the map grid array(1000 * 1000) in C, and when map blocks changed, Erlang calls 'updateBlock' NIF to update the grid state in grid array in C?

Thanks!




At 2017-07-11 00:33:34, "Dmitry Kolesnikov" <[hidden email]> wrote:
Hello,

On 10 Jul 2017, at 19.11, skyman <[hidden email]> wrote:

Hi everybody,

Our game is using A Star algorithm to find path. For performance I want to write it in C language, and Erlang calls it by NIF. I don't know whether the map data is maintained in C or in Erlang. Can anyone tell me?

Map is native data structure. However, you need to use enif interface to interact with it. 

In addition, is there any better solution than NIF?

I’ve used to solve a “routing” issues on pure Erlang using ETS, lists, etc. However, this mainly depends on your traffic, latency and size of routing tables. It is hard to give a straight forward answer not knowing this figures.      



Thanks very much!

Best Regards, 
Dmitry


 


_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions



_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Loading...