Stuck on improving navigation


#1

I am using python 3.
I am stuck on improving the navigation function. I have devised an A* implementation which is slower than the actual navigation. I tried a shorted line and circle collision detection which (for some reason) runs slower on the game but fast outside the game (?). My A* implementation optimization works fine outside the game ( so far it just finds coordinates to the goal ) as I just divide the map by a number and all the points by that number so it just has a close enough guess of points; this works outside the game perfectly fine but returns errors randomly during the game. I have even posted this at this link but the only help I received was to use C++ or Java which I don't have a good grip on to program at this level. Also, I am stuck on timeout errors and they are frustrating me alot.

Can anyone help me on the navigation logic improvements. I think I need to make a hit-map and then a route finding algorithm. But I don't understand how to.


#2

I'm working on this type of navigation:

After stumbling around for about 2 days I pieced together an algorithm that builds the gradient but it was taking 1.7 seconds to compute in pure python for a small map...
after eliminating some recursion and decorating with @numba.jit it now takes 170 miliseconds or so, so definitely look into numba as well.
That being said, your mileage may vary. I haven't actually implemented the navigation yet.


#3

Does the server come with numba? I know it comes with numpy


#4

It doesn't come with numba but you can pip install it
https://halite.io/learn-programming-challenge/downloads-and-starter-kits/customize-bot


#5

I am stuck on around 4.0 seconds for generating a vector field - more if I use @jit. Do you have any tips?


#6

I sure do!

numba has 2 different jit modes, 'object' mode and 'nopython' mode. Object mode runs no faster, or indeed sometimes slower than regular python. A lot of datatypes aren't supported within nopython mode, so jit functions that contain an custom classes, or dicts will product object mode code instead.
There is one caveat. Object mode code will run faster than regular python if it contains many loops that can be 'loop-jitted' I have no idea how this works, or how you can tell. I just trial and errored until I got it right.

You can see if a function works in nopython mode by decorating with @njit or @jit(nopython=True)

Create any necessary numpy arrays outside the jitted functions, and pass them in, don't create arrays inside jit functions. (I think returning new arrays used to be not supported. I think now it is supported but it is slightly slower)

How my code works:
I have 3 functions: 2 of them work in nopython mode and the third one takes advatage of loop-jitting.

@numba.njit
def get_neighbours(point, rows, cols): # takes a point as a tuple (x,y) and returns all of its neighbours that aren't off the map. Not strictly necessary as it's own function but it makes the loops cleaner without a performance penalty

@numba.jit
def explore_point(point_to_explore, rows, cols, inarray, dmask):
takes a point, runs get_neighbours() on it. Iterates through list it gets back.
for each neighbour, checks if dmask[neighbour] ==0
(# dmask is a numpy array initialized to zeros with the same shape as
the map. (inarray is the map)
inarray[neighbour] += (inarray[point_to_explore] + 1) #key piece of logic
This function then returns all of the neighbours it found that were not yet explored. (aka their mask was 0)

Third function runs the brushfire algorithm, and calls explore_point() in a loop it is decorated with @jit and runs in object mode. That being said, I dont use any halite special objects in it. Everything it knows about is either an array, a tuple or a list. I realize this is coming to the end of my post and I probably should've put it at the beginning, but don't pass any halite objects into a jit function, it is guaranteed to be slow then.
create a numpy array with the same shape as the map and set every cell that contains a unit to a 1. That array becomes the mask, and gets passed in to tell the algorithm which points are unpassable.
@jit
def jitfront(inarray, point, dmask ):
pointstoexplore = collections.deque() #This is why it runs in object mode. You can use a list if you want and it will compile in nopython mode and be an order of magnitude faster, but things seem to get weird for me.
pointstoexplore.append(point)
while pointstoexplore:
epoint = pointstoexplore.popleft()
for nextoexplore in explore_point(epoint, rows, cols, inarray, dmask):
pointstoexplore.append(nextoexplore)

I realize the formatting is all horrible. Hopefully finding out where the indents are will be part of the fun
Good luck!


#7

Thank you so much! However, I am confused by the inarray. How is your inarray structured and how do you edit the dmask if neighbour is visited and how is the inarray += to?
Is inarray structured like this in a list or a numpy.array or something else all together like a dictionary?

inarray = [ (0,0), (0,1),
            (1,0), (1,1),
          ]

Where your numpy.zeros is

np.zeros((2,2))
->
array([0. 0.]
      [0. 0.])

#8

both inarray and dmask are np.zeros(game_map.width, game_map.height, dtype= np.uint32 )
or swap the axes if you want to


#9

How did you check for obstacles? I can't add an array for all the obstacles and check in get neighbours - numba keeps giving errors.


#10

The obstacles are in the dmask array, although I'm still working on it. if you pass in an array that has 1's where ships and planets are located, the pathing gradient will automatically work around them
This picture has no ships or planets, but it has walls. The target point is 1,1 in the top left corner. You can see the path distance(brighness) gets higher as you go down the image, and then across on the right side, and back up to the top.
If you zoom in you can see the breaks in the walls.


#11

if you feed in a mask that looks like this

You get out a gradient that looks like this:

Obviously, the planets are the wrong colour and will cause all ships that are within 1 unit to crash into them so just use the same function you used to draw the planets, and draw them max brightness.

now the gradient next to a planet will always point away

In the image above the target was set to 0,0. This one has a more reasonably placed target

on my PC it takes ~51 miliseconds to generate that image


#12

I think that Best-First-Search algorithm would be better than A*, because it's much faster and map have no unclosed obstacles(only closed(planets) and points(ships) ). Compare pathfinding speeds on map with obstacles like planets on A* and BFS pathfinding algos there: http://qiao.github.io/PathFinding.js/visual/


#13

How did you generate a vector field? I used a dictionary with neighbours as keys and angles as values. Now I can't use numba. Also my execute times are still in 1.2-2 ... maybe my computer is slow - can you please tell me what computer you're using?


#14

All, there's a longish (and apparently popular) thread on an auto-learned vector field approach which you may find useful- its certainly working well for me.

https://forums.halite.io/t/concrete-info-top-100-with-rl-policy-gradients/892

Note that you only need the gradients at ship locations not at every point , so it is extremely efficient.


#15

Sorry, but I'm confused even after reading the topic as to how make a vector field only for ships.


#16

Convert your dictionary to a tuple or a list. Numba doesn't like dicts. I'll have a more complete source that I'll be willing to share by Sunday Jan 14th