search

ASPP / pelita_template

Default template to get started with the Pelita game.
3 stars 25 forks source link

remove/improve a_star example #8

Closed otizonaizit closed 5 years ago

otizonaizit commented 6 years ago

Remove the demo that uses the a_star for getting the next step to the target food. The example should be rewritten to store the shortest path and just recalculating it when the target changes. Right now it is terribly inefficient (the shortest-path is recalculated every time), but students used that for their own code. We should show instead how to store the shortest-path.

jni commented 5 years ago

I can confirm that this is an issue... =P

Debilski commented 5 years ago

The a_star example bot alone wouldn‘t profit from caching though. It only makes sense when you do many more searches (at least that’s what I found).

jni commented 5 years ago

What? LOL the problem is that utils.py has a function that takes a "graph" object and a function that builds a networkx graph, and every team has tried to use that function and then the move function, which expects a pelita.utils.Graph

otizonaizit commented 5 years ago

Hey @jni, can you come up with an implementation? Not too clever, just the bare minimum needed. The code will be most probably used by almost all groups, so it shouldn't give away all the tricks, but it should be reasonably efficient... @Debilski : what are you talking about?

otizonaizit commented 5 years ago

@jni another thing: we are going to have a pelita sprint in February, so please file issues and wishlists while you discover them in Canberra, OK?

Debilski commented 5 years ago

@otizonaizit Hmm, maybe I misread your issue anyway. I added some test code that just stored the full path in the state dict in demo04_basic_attacker.py (instead of only the target position and then calculating the a_star every step), but for the size of our mazes at least there was no speed difference (doing 1 a_star is not too expensive). Of course the problem is not in demo04 (which uses a_star explicitly) but in the other examples that do a lot more searches.

otizonaizit commented 5 years ago

I added some test code that just stored the full path in the state dict in demo04_basic_attacker.py

Where did you add it? Is this a PR or a branch or what?

(instead of only the target position and then calculating the a_star every step), but for the size of our mazes at least there was no speed difference (doing 1 a_star is not too expensive).

Good to know, but still, we want to show an example of how to do it the right way. It is redundant to recreate a networkX graph every time and recalculate the a_star path while you are following the very same path towards the very same target. So we need an example where this is done by caching the path and only recalculate the path when you have a new target or the enemy is in the way. And the networkx conversion should only happen once. This is just because of logic, not because of speed. The speed advantages, if any, are just a bonus.

Debilski commented 5 years ago

I never made a commit from the code because I felt it needed some more refining (and I did not 100% trust my logic that invalidated the cache) to make it more easy to follow. I can rework and add it but it is still a specialised cache for the go-to-next-food bot. Having a generic LRU wrapper around next_step is probably less error-prone and more helpful in all other cases.

otizonaizit commented 5 years ago

That has been fixed rewriting the demos that were using the shortest_path and by using only networkx for graph operations.