AStar in a specific case in C#

Hello.

To an intership, I have use the A* algorithm in the following case :

the unit shape is a square of height and width of 1,
we can travel from a zone represented by a rectangle from another, but we can't travel outside these predifined areas,
we can go from a rectangle to another through a door, represented by a segment on corresponding square edge.

Here are the 2 things I already did but which didn't satisfied my boss :

1 : I created the following classes : -a Door class which contains the location of the 2 separated squares and the door's orientation (top, left, bottom, right), -a Map class which contains a door list, a rectangle list representing the walkable areas and a 2D array representing the ground's squares (for additionnal infomations through an enumeration) - classes for the A* algorithm (node, AStar)

2 : -a MapCase class, which contains information about the case effect and doors through an enumeration (with [FLAGS] attribute set on, to be able to cummulate several information on each case) -a Map classes which only contains a 2D array of MapCase classes - the classes for the A* algorithm (still node an AStar).

Since the 2 version is better than the first (less useless calculation, better map classes architecture), my boss is not still satisfied about my mapping classes architecture.

The A* and node classes are good and easily mainainable, so I don't think I have to explain them deeper for now.

So here is my asking : has somebody a good idea to implement the A* with the problem specification (rectangle walkable but with a square unit area, travelling through doors)?

He said that a grid vision of the problem (so a 2D array) shouldn't be the correct way to solve the problem.

I wish I've been clear while exposing my problem ..

Thanks

KiTe

yes, but how should i determinate the weight then?

KiTe 2010-03-01 15:33:15

Can you just clarify: are you trying to find a route though a maze of rooms with doors in them? If so, is the distance between all connected rooms equal? If so, the weights can all be set to 1 (or any constant you like).

sfg 2010-03-01 15:54:37

"are you trying to find a route though a maze of rooms with doors in them?" --> yes"If so, is the distance between all connected rooms equal?" -> no, because the rooms are rectangle of different size, but they are all composed by the same unit square

KiTe 2010-03-01 15:56:39

Well each room has a node and the edges between the nodes need to be the distances to travel between each pair of nodes. You will have to calculate this for each pair.

sfg 2010-03-01 15:59:21

humm this method only allows to travel from a room to another, but not inside the room right? so if I want to go from a precise location inside a room to another precise location inside, it is not possible with your method

KiTe 2010-03-01 16:16:26

I thought you were traveling room to room, not square to square. Make the squares the nodes (now do you have constant weight edges?).

sfg 2010-03-01 16:22:19

so here we come to what I already did.In my solution, the squares are the nodes. Horizontal/Vertical edges have a weight of 10, and diagonal a weight of 14.The problem is if i want to store additional information about ground cases, I must create a 2D array...So I'm searching for a method which finally doesn't need this 2D array (and then the additional informations), to go from a precise location to another.

KiTe 2010-03-01 16:27:08

but keeping in mind that we must consider rooms ^^

KiTe 2010-03-01 16:27:43

So in your solution: each walkable square is a node with connected edges to other walkable squares. These squares are packaged into rooms which are rectangular. You also have other, non-walkable squares. These non-walkable squares are not in the graph and so you have stored them in a separate array (in which I assume all squares are stored). Is the problem: how to store these non-walkable squares (with all their attributes) without using a 2d array?

sfg 2010-03-01 16:39:46

if they are non walkable, we don't really care about their attributes.just forget the attribute for now, because this is not really asked in my subject (I just wanted to add it for fun, at first ^^)I just want to find a way to apply the A* algorithm from a specified location to another, which are into rooms, moving square by square

KiTe 2010-03-01 16:51:19

I do not understand the difficulty posed by the rooms. You need each square represented as a node with pointers to the connected nodes. If one square cannot enter another because they are separated by a wall then they should have no connection.. Run that through A* to get the route from start to goal. Nowhere in this is an array needed. What am I not understanding about the problem?

sfg 2010-03-01 17:04:27

at first sight i didn't see any difficulty either, but as I did my class architecture my boss said it was not optimised .. but i just kept the strict minimum.So I ask to see if someone has an idea I didn't already had ^^

KiTe 2010-03-02 08:45:11

ansaurus

tags:

views:

answers:

AStar in a specific case in C#

related questions