sorry but I’m a beginner. I have to see if between 2 plane adjacent to each other is a wall. How can I do without raycast?
Raycast, capsulecast boxcast you got a few ways. Or just put a collider their and check that way.
why “without raycasts”?
I’m basically doing an algorithm a star through a maze. The problem is that the walls are located between a node and the other. So I have to see if the two nuts is a wall
That still does not answer why no raycasts since using one will be the most efficient way to do what you want.
most A* algorithms I’ve seen are node based and the information about what nodes are connected to each other is all held in the node data as a part of the map data structure… i.e. if a wall is between two nodes they don’t have a “link” between them.
or are you at that stage and you’re building the node map?
1 Like
This has been a hot topic the last few days…
You should be creating graphs that are searched by the path finding algorithm.
Either you can build the graph manually by hand (drop down nodes, wire up paths between nodes).
You can have a scanning algorithm that runs at design time that builds the graph (useful for scans that may be intense).
You can have a scanning algorithm that runs at runtime that builds the graph (either at load time, or if it’s a fast scan, mid game-play to update any moving objects like doors).
Scanning is great for figuring stuff out, but can have problems with organically shaped levels as it might screw up edges.
Manual is slow as all heck, but it gives you full control.
And you can of course write a design time scanner that then let you modify small parts manually.
I have read that one user has the same problem. But the problem is that I do not understand. The algorithm works astar me if the wall is in a cell. But if the wall is located between a cell and the other does not know how to explain that that area is occupied
A* does not know about walls…
An A* is a node graph traversal algorithm. It gets a graph of nodes, and it finds the best path through it to get from one node to another.
A graph is a collection of nodes, and the relationships between them (which nodes neighbour which… I can go from A to B, but not A to C).
You need to build the graph BEFORE you run A* algorithm on the graph. What you do is define which nodes neighbour eachother. You can do this by ‘scanning’ the area. You go through your list of nodes one by one, and find the ‘best neighbour’, then raycast to see if there’s a wall between them. You store this data with the nodes in the graph.
Then the A* algorithm usually calls a ‘GetNeighbours(node)’ method that returns what nodes can be directly traversed to from the input node. The graph should return the nodes that the scan calculated.
For more info on graphs check out wikipedia, and then research from there:
Note how the graphs are all nodes with lines between them.
A* would help you find the best path between 6 and 1, by asking the graph what neighbours 6 has (4), then what neighbours 4 has (5,3), then the neighbours of those, etc until it finds the least costly route (usually the paths have weights assigned to them, a distance heuristic, a node cost, etc…)
Both you and @Bolt need to separate the concept of the graph from the concept of the A* algorithm. They’re only related in that the A* needs a graph, but A* doesn’t care how a graph is defined… just that it IS defined.
I even showed a basic contract for the graph here:
I showed a VERY basic open GridGraph with no walls… you need to write your own IGraph that instead of a square array of nodes… you have nodes and neighbour information.
(note - that example is not gospel, it isn’t even the best option… I slapped it together for example sake written directly in the browser… it is untested and so on so forth. DO NOT copy paste it. Read it and understand what I’m attempting to do)
1 Like
you use the nodes I understood, it was not clear that it must ignore the walls. Therefore they must be used to force the raycast? thank you
I’m not sure what this question means.
Could you rephrase it?
I understand that it appears English is not your primary language…
sorry, but I’m not good with English. The raycast uses the enemy when he walks or do I have to apply the algorithm?
No, you use the raycast when building the graph. Whenever you build the graph.
The A* algorithm is used to traverse the graph once built.
You only have to build the graph once, unless it changes (a wall moves).
I use the raycast to “create” the shortest route? I think I’ll keep you informed (if you’re willing to help me), thanks a lot for everything
Not to create the shortest route. But to define the neighbours for each node.
So then the shortest route can be found with the A* algorithm.
Basically, enumerate through all the nodes, raycast to each possible neighbour, if a wall exists drop it from its list of neighbours.
this is my code. Do you think I’m heading in the right way?
[using UnityEngine;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
namespace blablabla
{
[System.Serializable]
public class Node
{
public float G { get; set; }
public float H { get; set; }
public float F { get { return this.G + this.H; } }
public bool isWalkable { get; set; }
public Vector3 position { get; set; }
public GameObject floor;
public int current { get; set; }
}
public class GenerateCell : MonoBehaviour
{
private List<Node> nodes;
[SerializeField]
private GameObject floor;
private Vector3 startPosition;
[SerializeField]
private int xSize;
[SerializeField]
private int ySize;
private List<GameObject> allCell;
private List<Node> openList;
private List<Node> closedList;
private List<Node> neighboringNode;
[SerializeField]
private int range;
[SerializeField]
private GameObject wall;
[SerializeField]
List<Node> adjacentNodes;
public Node startNode, currentNode;
void Awake()
{
startPosition = new Vector3(0f, 0f, 0f);
allCell = new List<GameObject>();
nodes = new List<Node>();
openList = new List<Node>();
closedList = new List<Node>();
neighboringNode = new List<Node>();
adjacentNodes = new List<Node>();
createFloor();
createNode();
createWall();
}
void createFloor()
{
for (int i = 0; i < xSize; i++)
{
for (int j = 0; j < ySize; j++)
{
GameObject instantiate = Instantiate(floor, new Vector3(i, 0f, j), Quaternion.Euler(90f, 0f, 0f)) as GameObject;
instantiate.name = ((i * xSize) + j).ToString();
allCell.Add(instantiate);
}
}
}
void createWall()
{
for (int i = 0; i < nodes.Count; i++)
{
if (nodes[i].isWalkable == false)
Instantiate(wall,
new Vector3(nodes[i].position.x, nodes[i].position.y + 0.5F, nodes[i].position.z),
Quaternion.identity);
}
}
void createNode()
{
for (int i = 0; i < xSize * ySize; i++)
{
nodes.Add(new Node());
nodes[i].floor = allCell[i];
nodes[i].position = allCell[i].transform.position;
nodes[i].current = i;
nodes[i].isWalkable = true;
}
pathFind(nodes[12], nodes[84]);
}
float setG(Node starPosition, Node currentNode)
{
Renderer testG;
float valueG = heuristic(starPosition, currentNode);
testG = currentNode.floor.GetComponent<Renderer>();
testG.material.color = Color.green;
return valueG;
}
float setH(Node currentNode, Node endNode)
{
Renderer testH;
float valueH = heuristic(currentNode, endNode);
testH = currentNode.floor.GetComponent<Renderer>();
testH.material.color = Color.green;
return valueH;
}
float heuristic(Node firstNode, Node secondNode)
{
float manhattanDistance = Mathf.Abs(secondNode.position.x - firstNode.position.x) + Mathf.Abs(secondNode.position.z - firstNode.position.z);
return manhattanDistance;
}
void findNeighboards(Node currentNode)
{
for (int i = 0; i < nodes.Count; i++)
{
if (Vector3.Distance(currentNode.position, nodes[i].position) == range)
{
if (nodes[i].isWalkable)
adjacentNodes.Add(nodes[i]);
}
}
}
void debug()
{
for (int i = 0; i < neighboringNode.Count; i++)
{
Renderer r;
r = neighboringNode[i].floor.GetComponent<Renderer>();
r.material.color = Color.yellow;
}
}
private void pathFind (Node start, Node end)
{
openList.Add(start);
while(openList.Count != 0)
{
Renderer r, r2;
Node currentNode = openList.OrderBy(minValue => minValue.G).First();
r = currentNode.floor.GetComponent<Renderer>();
r2 = end.floor.GetComponent<Renderer>();
r.material.color = Color.blue;
r2.material.color = Color.red;
openList.Remove(currentNode);
if (closedList.Contains(currentNode))
break;
findNeighboards(currentNode);
foreach (Node item in adjacentNodes)
{
if (closedList.Contains(item))
continue;
//if (!openList.Contains(item))//se non è nella open list, ignora
//{
float g = setG(start, item);
float h = setH(item, end);
Debug.Log(item.current+": " +(item.G + item.H));
//
//
// openList.Add(item);
//}
}
adjacentNodes.Clear();
}
}
}
}