1. Member
Join Date
May 2012
Posts
30
Rep Power
0

## Re: Advice for a NPC Path Algorithm

Yes, I've seen that animation before. And alright. I believe that Java has a similar function built into it for the Map class. And yes, I am familiar with C++. I used it for my course last year. By now, I probably know Java better though, just because of the fact that we are doing more complicated things with it. Thanks again! By the way, did you get my PM?

2. Member
Join Date
Jun 2012
Posts
23
Rep Power
0

## Re: Advice for a NPC Path Algorithm

Yes, I just noticed your PM and I replied. And yes, it have a similar function. It is Map<Key,Value>#containsKey(Object). So you can check if the node is visited doing visited.containsKey(node).

3. Member
Join Date
May 2012
Posts
30
Rep Power
0

## Re: Advice for a NPC Path Algorithm

Hmmm, it doesn't seem to want to end the first loop ever. I tried outputting visited and it returns null... I'm thinking that something isn't working as it should. Thanks again!

4. Member
Join Date
Jun 2012
Posts
23
Rep Power
0

## Re: Advice for a NPC Path Algorithm

Just let me see your code. Sounds like you didn't initialized 'visited' at all.

Originally Posted by Grimey
EDIT: By the way, I have created a map using the java.util class which stores the node and integer, like this:
Java Code:
`Map<Node, Integer> visited = new HashMap<Node, Integer>();`
I have no idea how to manipulate it though.
A map is a non-linear data structure that asigns to a unique key a value.

A map of <integer,object> would be like a vector (in C++)

Java Code:
```vector<double> a(100);
map<int,double> b;
a[0] = 15.4;
b[0] = 15.4;```
Those looks like they are the same (even they are not). A quick (very quick) summary is that a vector is lineal data structure, that is efficient in time when you need to get or set a value. A vector is inefficient for space, as you can not have non-linear keys (that is, you cannot have a[10000] = 14. without allocating 10000 doubles).

So in BFS is better to have a Map instead a vector, because you rarely will check every node.

I suggest you to learn about data structures, as vector and maps have very different properties.
Last edited by lilezek; 06-13-2012 at 12:36 AM.

5. Member
Join Date
May 2012
Posts
30
Rep Power
0

## Re: Advice for a NPC Path Algorithm

Okay. I will look into that. I emailed you the code for the game. Most of the stuff for the BFS algorithm is in the BotDat class. I will definitely be looking into data structures methinks. Perhaps it would be best if I made yet another class?

EDIT: Wait, I am a little lost. I was looking at the documentation for the Map class in Java. It seems like it acts ALMOST like a linked list with a pair <Node, Integer> in my case. It looks like it won't take on things twice though, so wouldn't that mean that it will at most have 2500 nodes for my purposes, as my map is 50x50. This is certainly complex. I am really enjoying it though! And sorry if I am seeming pretty novice to you! Haha
Last edited by Grimey; 06-13-2012 at 01:06 AM.

6. Member
Join Date
Jun 2012
Posts
23
Rep Power
0

## Re: Advice for a NPC Path Algorithm

If your map is 50x50 you can even take a bidimensional vector (as you are not going to have run out of memory problems). If you can't understand the difference between linked lists and maps, you could check out videos or images (that REALLY will help you to understand those) or ask your teacher.

The main difference is that if you use a linked list of a pair, and you need to find an element, you will be penalized with some time (the complexity of search in a linked list is linear of its size). If you use the Map, you will be penalized with less time than linked list (the complexity of seach is logaritmic of its size, because Maps are somehow sorted).

Is like if you have one million elements, you are going (in the worst case) to iterate over one million elements with the linked list. But if you use a Map, you are going to "iterate" over
(more or less) 20 elements. This is a great decrease of time.

Just compare linked list with balanced tree (which is usually the algorithm choosen for Maps):

By the way, in a 50x50 map you won't notice any difference between those. If you really want to feel the difference, go to a 1000x1000 Map and try to access data from there, using a linked and using a map. You will notice huge lag using linked list, and normal lag (as you have a million of elements) with the Map.
Last edited by lilezek; 06-13-2012 at 02:26 AM.

7. Member
Join Date
May 2012
Posts
30
Rep Power
0

## Re: Advice for a NPC Path Algorithm

Not sure this machine would handle it at all. I'm only getting about 20 FPS now. It's an old thing I got for off someone so I could use it for Linux. Still better than no laptop. Haha. And alright, time to do a little research... Thanks again!

Page 2 of 2 First 12

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•