A* in SimCity201

[dwilczyn]

Don't forget to look at: https://github.com/usc-csci201-fall2013/astar

for the issue tracker on A*

[diegovb]

Has it been decided if this is a requirement or not? Would it be a requirement everywhere or just for one feature it's enough?

Thanks!

[dwilczyn]

A* is not a requirement. I will probably do an in depth look at the code this week in class (wed and thurs).

[lizhifan]

I have tried implementing A* and was having success when I had only one bus. However, once i added another bus, I kept getting the error that eclipse ran out of heap space. I was wondering if there was any way to remedy this. I am using a grid of 30 x 30, which I realize is an extremely large amount of choices for A* to have to run through.

[dwilczyn]

Obviously, people are struggling with A* because of the heap space problem. Frankly, it's not obvious to me why unless it has to do with gridsize. I never got a heapspace overflow in my restaurant and it had many waiters moving around probably because finding a solution was easy because of the gridsize.

You should reduce the gridsize and simplify your paths until your A* performs reliably. Don't spend too much time here, you have many things to do.

I wonder if eclipse has something to do with this. Can someone try to run their code outside of eclipse? You can do it on aludra or create a full java environment on your pc. Maybe a CP can take on this challenge using some student's code?

[dwilczyn]

I have another idea. In any call to expanfunc() up to 8 new nodes are put on the nodes list. What if you only put the top TWO nodes on the list. That would be an easy fix. Implications: 1) A* might find a solution but it won't be optimum. That's not a big deal. 2) A* might NOT find a solution, returning NULL. One of the nodes you pruned off by only putting 2 on list might be the one leading to a solution. That is a big deal. What could you do then? Recompute without pruning? But that might lead to heapspace overflow. Recompute by adding at most 3 nodes? Not a bad idea, then you'd have to add a parameter to A* to indicate this number, not very hard.

Can someone try this?

[dwilczyn]

I have another idea. If A* has to produce LONG paths, it runs into the space problem. If you decompose the grid into areas and make A* only look within an area, it has a better chance. So then your original A* in looking for a path in the full grid, is now changed into, for example, 3 calls to A* looking for a path in area 1, then from area 1 to area 2, then from area 2 to area 3 where the destination, the problem is MUCH easier for A*.

FedExpress surely does this when doing its package distribution problem. They have to solve the famous Traveling Salesman problem, which is intractable for large spaces. So, they decompose the map into regions and solve lots of smaller problems.

This is not so easy. How do figure out which areas to move through? How do you know which square is the TRANSITION square between areas? Can there be more than one transition square? I'll have to think about this.

If someone wants to try this, I'll help.

[mktrevor]

I was just able to significantly reduce the amount of time needed to compute routes by having the expandfunc() disregard all diagonal movements. This way, agents can only move up/down or left/right, so only 4 nodes are added to the node list, but it will still find a path if one exists every time. I may try to combine this with one of Professor Wilczynski's ideas to make the animation move even more smoothly.

[dwilczyn]

Excellent work by trevorar. A* can often be given APPLICATION specific help in order to improve its performance. Everything is fair game in this kind of business. Solving hard problems is hard...and gratifying. The best kind of work.

[jchand]

Removing diagonal movement was a really great idea and it definitely sped up my algorithm - but I'm still getting lag fairly often.

Right now I have a 60x60 grid with 16 buildings (4x4) - I might be able to bring it down to 9 buildings (3x3) but that would require multiple "floors" for each building (for example, one building would have five floors with five restaurants). Would that be acceptable?

[dwilczyn]

Of course.