Member Avatar for DarkLightning7

Ok so im working on a mapping library for my pathfinding system and im trying to figure out what Data structure would be best to use for rapid calls up to several hundred a second, as low memory usage as possible, and not too difficult to store and load pieces(chunks) of the map from a sql relational database.

Here is the scenario:

  • The map is devided up into sections called chunks for lack of a better term. Each chunk is connected by any number of links to its neighboring chunks if there is a way to walk from one chunk to the other.

  • Each link is connected to every other link in its 2 associated chunks provided there exists a path between the links. The cost to travel to any directly connected links along with other data. Connections between links may have direction.

  • The links might need to be confined to their chunk with a reference to the link on a neighboring chunk instead of the link be associated with 2 chunks. Just an idea for easier storage and retrival.

Im looking for a good way to store the link list for each chunk where it is easy to search with AStar and Dijkstra and only a portion of the chunks may be in memory at any time.

Any possible improvements to the design are welcome

If any part of this is confusing please say so ill try to explain it better.

Thanks.

Edited by DarkLightning7
  • 2 Contributors
  • 2 Replies
  • 203 Views
  • 13 Minutes Discussion Span
  • Latest Post Latest Post by DarkLightning7
Member Avatar for iamthwee

If it's djikstra then just use whatever the defacto data storage method for djikstra is.

So in short any heuristic solution for the all to common travelling salesman type problem is what you need I would have thought.

Edited by iamthwee
Member Avatar for DarkLightning7

Dijkstra works with a lot of data storage methods its not too picky I just included it for completeness sake. It also needs to be concurrent access friendly.

Thanks for the quick reply.

Edited by DarkLightning7
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.