|
I agree!
"Program testing can be used to show the presence of bugs, but never to show their absence."
<< please vote!! >>
|
|
|
|
|
SOLVED
For anyone interested here is the solution to my problem:
public IEnumerable<Tile> PathFind(Tile startNode, Tile endNode)
{
List<Tile> openNodes = new List<Tile>() { startNode };
List<Tile> closedNodes = new List<Tile>();
Tile lowestFScore = null;
while (openNodes.Count > 0 && lowestFScore != endNode)
{
lowestFScore = GetLowestScoringTile(openNodes, endNode);
openNodes.Remove(lowestFScore);
if (lowestFScore == null)
return null;
SwitchFromOpenToClosedList(lowestFScore, openNodes, closedNodes);
IEnumerable<Tile> neighbouringTile = GetNeighbouringTiles(lowestFScore);
foreach (Tile n in neighbouringTile)
{
if (IgnoreTile(n))
{
SwitchFromOpenToClosedList(n, openNodes, closedNodes);
continue;
}
if (closedNodes.Contains(n)) continue;
if (!openNodes.Contains(n))
{
openNodes.Add(n);
n.Parent = lowestFScore;
}
}
}
return RenderToGrid(endNode);
}
I have done my research and attempted several times to create my version of the infamous A* path-finding algorithm.
The algorithm I have made does seem to work though!...(unsurprisingly)
If anyone can help me it would be great, I am sure it is just a logic problem in the main part of the method:
public void PathFind(Tile startNode, Tile endNode)
{
List<Tile> openNodes = new List<Tile>() { startNode };
List<Tile> closedNodes = new List<Tile>();
Tile currentNode = startNode;
while (true)
{
foreach (Tile n in GetNeighbouringTiles(currentNode))
{
if (closedNodes.Contains(n)) continue;
if (IgnoreTile(n))
{
if (!closedNodes.Contains(n))
{
closedNodes.Add(n);
continue;
}
}
n.Parent = currentNode;
if (!openNodes.Contains(n))
openNodes.Add(n);
}
if (openNodes.Contains(currentNode))
openNodes.Remove(currentNode);
Tile lowestScoring = GetLowestScoringTile(openNodes, endNode);
if (lowestScoring == null) lowestScoring = currentNode;
if (openNodes.Contains(lowestScoring))
{
openNodes.Remove(lowestScoring);
}
foreach (Tile n in GetNeighbouringTiles(lowestScoring))
{
if (closedNodes.Contains(n)) continue;
if (IgnoreTile(n))
{
if (!closedNodes.Contains(n))
{
closedNodes.Add(n);
continue;
}
}
n.Parent = lowestScoring;
if (!openNodes.Contains(n))
openNodes.Add(n);
else
{
if (Tile.GetCost(lowestScoring, endNode) > Tile.GetCost(n, endNode))
{
n.Parent = lowestScoring;
lowestScoring = n;
}
}
}
currentNode = lowestScoring;
if (openNodes.Count == 0 || currentNode == endNode)
return;
}
}
I am expecting the method to return when there are no more nodes remaining (which tells me that there is no way of getting from a to b), or the current node is the end node (which should mean that I can just re-curse through each "Parent" attribute of the endNode to cycle through the path.
Edit1: I noticed that the first " n.Parent = currentNode;" is never reached!
Edit2: The "GetNeighbouringTiles" method was incorrect, it didn't search for moving down... The pathfinding method hits an infinite loop now...
It only ever does the former result 
modified on Tuesday, January 4, 2011 1:40 PM
|
|
|
|
|
|
Thank Espen,
I was trying to do it based on the concept, I didn't want to use other code and instead build from the concept 
|
|
|
|
|
|
.. A few comments on this, if your using XNA and want to use this code on the XBOX, you should get rid of the Foreach loop, it is a performance killer due to GC on the XBOX....
Also you should look into the weighting Heuristics, because this approach albeit closed and complete is not as efficient as it could be....
Also your sucking up memory as you use this algo... have you tested it against a large number of bots representative to the normal in game load...., I'd wadger it won't run inside your game loop propperly for more then 125 or so bots (using a 256x256 tile map).... just trying to give you the heads up...
I'd blame it on the Brain farts.. But let's be honest, it really is more like a Methane factory between my ears some days then it is anything else...
-----
"The conversations he was having with himself were becoming ominous."-.. On the radio...
|
|
|
|
|
I used to be pretty good at this stuff, but I just can't get a handle on how to express this properly. Thirty years takes a toll on remembered math, so I hope someone more recently experienced with probability can steer me back on course.
In the game of Keno there is a field of 80 numbers, from which 20 are selected for each round. Players pick from n = 3 to 20 numbers and hope that n of them will come up in the next round. In reality, far fewer than n usually pop up, and I'd like to know the probability of each combination occurring. For instance, suppose I pick 6 numbers. How can I calculate the probability that 3 of my numbers will be among the 20 drawn? 5?
The simple approach of calculating draws doesn't work, since the classic method I remember determines the probability of all 3 numbers coming up in 3 draws. But given that 20 draws are made regardless of how many I pick changes things considerably. I just can't figure out how to express it.
Anyone care to take a crack at it?
Will Rogers never met me.
|
|
|
|
|
DISCLAIMER: This could be totally wrong...
Ok, so I start by saying there are 80 squares - 20 of which are picked each round. Intuition says now:
20/80 = 1/4 = 25%
A colleague said "It's not that simple, because not ALL the 80 are picked each round." I justified my answer by saying replace this with a coin, there are two possible outcomes. If you flip it once, not ALL the outcomes are going to be achieved, but it's still a 50% chance (statistically speaking, none of this "the Queen's head is heavier BS").
Anyway, back on track, this would mean that for each individual number on the board, there is a 25% chance it will be picked in a given round. Therefore, for the three numbers YOU selected to ALL come up:
(if you say 'and' it means multiply, 'or' is addition (off the odds))
for outcomes: N1 and N2 and N3
prob = prob(N1) x prob(N2) x prob(N3)
= (1/4) ^ 3
= 1/64
So, to generalise this, as no two numbers have different probabilities:
for outcomes: N1, N2 ... Nz
prob = prob(N1) x prob(N2) x ... x prob(Nz)
= (1/4) ^ z
= 1/ (4 ^ z)
So, for any selection of Keno numbers of length z, the probability of getting all of these is:
1 / (4 ^ z)
For more complex things like "if I pick 10 numbers, what's the chance of getting 8 of them" look up Permutations and Combinations - I cannot for the life of me remember the details, I just know one is concerned with the order of the outcomes and the other is not.
Anyway, statisticians, am I even close???
|
|
|
|
|
Well, you're close, but not all numbers have the same probability of coming up.
The first time you draw a number there is a 1/80 chance of it being a particular number. But the second time, the chance is 1/79, since the first number is not replaced.
I looked at it as the red ball/ black ball problem, where the number I picked are red balls. If I pick 10 numbers, then there are 10 red balls and 70 black balls. The probability of one of my numbers coming up ( order isn't important) on the first draw is then 10/80. The probability of of the second ball also being one of my numbers, given that the first was a good one, is 9/79, since I only have 9 numbers remaining in the bag, and a total of 79 balls altogether. So the total probability of the first two balls being ones I picked becomes (10/80)*(9/79). That's easy enough to calculate. But how do I calculate the probability of perhaps, the 2nd, 9th, 11th, 12th, and 17th ball being good ones? Even if I make this tedious calculation for all the possible draw/hit combinations and orders, how do I determine the total probability of any particular number of hits in all the different orders in which they may occur? That's where I get stumped!
I think this may need to enter the domain of set theory, and calculating the probability that n of my numbers will be in a set of 20 numbers drawn from a field of 80.
My reason is quite pragmatic. There are different payouts for each combination of numbers picked and number hit in a round. And each game has different payouts. And to make it more interesting, each casino nmay have different payouts for the same games. If I can figure the odds on each combination, then multiply each by the payout for each machine and casino, I can learn which combination is optimal for each game and casino. I know that none of them is going to be a paying proposition, but I see no reason not to optimize my chances on a game I'm going to play anyway.
Will Rogers never met me.
|
|
|
|
|
Roger Wright wrote: The first time you draw a number there is a 1/80 chance of it being a particular number. But the second time, the chance is 1/79, since the first number is not replaced.
Damn it! I knew I'd forgotten something, oh well... never mind.
Roger Wright wrote: Even if I make this tedious calculation for all the possible draw/hit combinations and orders, how do I determine the total probability of any particular number of hits in all the different orders in which they may occur? That's where I get stumped!
That smells like Permutations and Combinations - in fact, I'd be surprised if this was not exactly what you were looking for: Permuations[^] and Combinations[^].
I believe you want Combinations, as (forgive me if I'm wrong) I don't remember the order of numbers mattering in Keno.
|
|
|
|
|
Excellent links, and I will look at them closely. But in the meantime, take a look at Luc's answer. It's quite a nice approach to the problem!
Will Rogers never met me.
|
|
|
|
|
Hi Roger,
the easiest way to tackle this is by reversing the chronology:
assume there are 80 numbers (1 to 80). Now let them first pick 20 "good" numbers out of those 80; it could be they pick numbers 1 to 20, and leave 60 "bad" numbers numbered 21 to 80; or any other combination, it does not really matter.
Then you pick N arbitrary numbers out of the range 1-80, each of them obviously has probability 20/80 or 1/4 of being good and 60/80 or 3/4 of being bad.
What you pick is represented by the expression (g+b)^N with g=1/4, b=3/4, and N the number of numbers you pick.
The expression equals 1 because g+b=1; however expanding the power series (using binomial coefficients), you get separate terms each representing a specific number G of good picks and B bad picks.
The probability that corresponds with a specific value of G and B equals COMB(G,N)*(g^G)*(b^B)
where COMB(G,N)=N!/G!/(N-G)!
Note: COMB is symmetric, i.e. COMB(G,N) = COMB(B,N)
As an example:
we continue with g=1/4, b=3/4
assume you pick 2, hence N=2
three possible outcomes:
2 good, 0 bad; hence G=2, B=0; probability = COMB(2,2)*(0.25^2)*(0.75^0) = 1 * 1/16 * 1 = 1/16
1 good, 1 bad: G=1, B=1; prob= COMB(1,2)*(0.25^1)*(0.75^1) = 2 * 1/4 * 3/4 = 6/16
0 good, 2 bad: G=0, B=2; prob= COMB(0,2)*(0.25^0)*(0.75^2) = 1 * 1 * 9/16 = 9/16
check: the sum of all three is 16/16 or 1.
PS: by looking at it in this way, there is no order, hence no 80,79,78... concerns!
|
|
|
|
|
The elegance of your solution is exquisite, but my recall of theory is too inadequate to judge the validity. I will take it as a working hypothesis and test it with real money. If all works out, there will be something nice in your stocking next Christmas.
Thanks, Luc - yet again!
Will Rogers never met me.
|
|
|
|
|
Luc's answer is the combination formula I linked you to
Just between you, me and the gatepost rest of CP, you're not actually going to use this with real money are you? 
|
|
|
|
|
GlobX wrote: you're not actually going to use this with real money are you?
Sure! I play a little Keno in any case, so why not approach it scientifically?
Will Rogers never met me.
|
|
|
|
|
Because the house edge in Keno is the among the highest in the casino.
Better to run over to the roulette wheel and put the same money on red or black. You'll still lose it, but at a much lower rate.
|
|
|
|
|
Ah, you're just not in the spirit of gambling! 
Over time, all casino games (except Craps) favor the house. But people do get lucky and nail a large win before losing a like amount. That hope is what keeps the industry alive. I have personally hit 6 of 6 on Keno twice this year, which pays off about 360:1, within the first few minutes of play. From years of playing, and watching players, I've learned that only one strategy works - play for a short time, and if nothing hits, walk away. If you do get a big win early on, walk away with it. That last is the hardest, by the way. It's really tempting sometimes to think that the machine is on a winning streak and more will follow. It does happen, but not often enough to make it worth trying.
Will Rogers never met me.
|
|
|
|
|
I could come up with some formula's for red and black probabilities on the roulette...
|
|
|
|
|
Roger Wright wrote: Over time, all casino games (except Craps) favor the house.
In general all games in which the house pays the players favors the house.
Variations of this are because the way in which the odds were calculated was flawed or because the game itself is flawed.
Those variations very seldom occur. They often involve odd circumstances. And casual play will not reveal it because such play would quickly expose such problems as the house take would not be following the expected income.
|
|
|
|
|
Cannot validate it myself but have a 5 just for such a good looking answer
return 5;
|
|
|
|
|
This problem has been well worked over, if you google Keno Probability you can even find source code to work out the expected return over a range of bets.
From what I have seen though, all expected returns on $1 are less than $1, so on average you will come out in front if you leave the dollar in your pocket. Where I live these are simple government revenue raising schemes that prey on the vulnerable (somewhat ironically the same folks the government supports).
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
|
|
|
|
|
I agree, the probability of winning at gambling is always less than 50% (usually a lot less) otherwise there would be nowhere to gamble
return 5;
|
|
|
|
|
musefan wrote: always less than 50%
not quite. The way roulette works, they win when 0 gets drawn, as it isn't considered part of any combination (red, black, less, more, odd, even, etc), so for any 37 units you play, you can expect 36 to return and 1 to loose. That's about a 3% profit on all the stakes for every turn of the table, not too bad for the casino.
|
|
|
|
|
Actually, sometimes a casino relies on people's lack of knowledge. There are two games in which people who play correctly will come out ever so slightly ahead of the house. They are straight video poker and craps. Even so, people routinely go for the big bucks ahead of their odds and loose plenty of money to the house. In theory you can also get ahead of the odds in Blackjack if the house allows it. But they guard against card counting quite well in the large gaming centers.
In Keno, the best strategy is to not think you can beat the system. So don't play unless the enjoyment of playing is worth the cost of loosing every time you purchase. I don't see a huge difference between a person who spends say $20 at a theater for two hours of enjoyment and one who spends $20 playing Keno for a couple hours of enjoyment.
|
|
|
|
|
Kirk Wood wrote: I don't see a huge difference between a person who spends say $20 at a theater for two hours of enjoyment and one who spends $20 playing Keno for a couple hours of enjoyment.
Exactly. Playing Keno is about as interesting as watching a PC run while betting that an alpha particle will take out a bit in the RAM. The odds are similar, too. But my favorite lady loves the game, and luckily prefers to play $.05 at a time, so I can spend hours of "quality time" with her for the price of a movie ticket and popcorn. Once in a while, she hits a big one and it really brings a smile to her face! Last week she hit 6 out of 6 on my birthday, and that was in a bonus round when jackpots are doubled. A win of $300 on a bet of 5 nickels is nothing to sneeze at, and creates a lot of joy for a lady with too little of it in her life.
I knew about craps, but I don't play it as it is awfully fast and intimidating to me; I just don't understand the rules, I guess. But I didn't know that straight video poker has a slight edge for the player. I usually play the Double Double Bonus poker, because of the payout for a 4 of a kind with a 'kicker', even though I know the lower hands pay out less than normal. What would be an optimal selection strategy for normal video poker? For example, in DDB poker, pairs are preferred over a single face card, as a pair of face cards pays even money, but 3 of a kind pays 3 to 1. In Deuces Wild, I save 2s and pairs, because Jacks or better pays nothing. Is there a strategy that works best for the stright poker game?
Will Rogers never met me.
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
